Zadanie
Každý úradník v Kanianke je spoľahlivý alebo nespoľahlivý. Tarzan potrebuje zapísať svoje deti na matrike. Žiaľ, jemu priradený úradník je nespoľahlivý. Navyše každý úradník v Kanianke pošle svojho zákazníka za svojím najobľúbenejším kolegom. Jeden úradník môže byť najobľúbenejší pre viacero svojich kolegov. Názory úradníkov sa v čase nemenia, teda daný úradník má celý život toho istého najobľúbenejšieho kolegu. Pre každé prvočíslo \(p\) platí, že po tom, ako bol Tarzan poslaný \(p\)-krát za ďalším úradníkom, sa nachádza u spoľahlivého úradníka. Podobne pre každé kladné celé číslo \(n\), ktoré nie je prvočíslom, platí, že po tom, ako bol Tarzan poslaný \(n\)-krát za ďalším úradníkom, sa nachádza u nespoľahlivého úradníka. Dokážte, že úradníkov v Kanianke je nekonečne veľa.
Dokazovať, že niečoho je nekonečne veľa, vyzerá byť tvrdý oriešok. Asi najjednoduchší spôsob, ako niečo také dokázať, je postupovať sporom – predpokladať, že úradníkov je iba konečne veľa a vyvodiť z toho niečo, čo určite nebude platiť. Potom náš predpoklad konečného počtu úradníkov musel byť nesprávny a je ich teda nekonečne veľa.
Prepokladajme teda, že úradníkov je konečne veľa a označme ich počet \(u\). Úradníci si Tarzana posielajú medzi sebou, každý ho pošle vždy za tým istým. Tarzan chodí stále za ďalšími a ďalšími úradníkmi a keďže tých je konečne veľa, časom sa musí nejaký zopakovať – konkrétne po návšteve \(u+1\) úradníkov sa už musel nejaký zopakovať, keďže ich je len \(u\) rôznych. Keď sa úradník zopakuje, je zrejmé, že Tarzan začne chodiť v kruhu, pretože to, za kým ho úradník pošle, závisí len od toho, pri kom stojí. Čiže keď v dvoch rôznych časoch stojí pri tom istom úradníkovi, celá postupnosť ďalších úradníkov bude rovnaká.
Za jedným úradníkom môže byť Tarzan poslaný od viacerých iných, takže jeho cesta má nejaký začiatok (predperiódu, ktorá môže byť prázdna, ale nemusí) a potom sa začne cykliť.
Vezmime si teraz nejaké prvočíslo \(p > u\). Také existuje, pretože prvočísel je nekonečne veľa, ale čísel menších alebo rovných \(u\) je len konečne veľa. Po \(p\) presunoch Tarzan stojí u spoľahlivého úradníka a zároveň už určite je na cykle, po ktorom bude chodiť donekonečna. Pokúsime sa ukázať, že po vhodnom počte prechodov cyklu bude poradové číslo toho istého úradníka zložené, a teda úradník by mal byť nespoľahlivý. To vytvorí spor, pretože ten istý úradník má byť spoľahlivý aj nespoľahlivý zároveň, čo je očividne nezmysel.
Označme dĺžku cyklu \(n\) (počet úradníkov, resp. počet presunov na ňom, je to to isté číslo). Potom k tomuto spoľahlivému úradníkovi príde Tarzan po \(p\), \(p+n\), \(p+2n\), \(\dots\) krokoch. V tejto postupnosti chceme nájsť zložené číslo. Tu si stačí uvedomiť, že stačí po cykle prejsť \(p\)-krát, to bude Tarzan mať za sebou presne \(p+pn = p(n+1)\) presunov, čo určite nie je prvočíslo, zapísali sme ho ako súčin dvoch činiteľov väčších ako \(1\). Mal by teda stáť u nespoľahlivého úradníka, ale tento úradník bol aj \(p\)-ty v poradí, a teda spoľahlivý.
Náš predpoklad, že úradníkov je iba konečne veľa, nás doviedol ku sporu. Úradníkov preto musí byť nekonečný počet.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.