133. feladványunkban Hókuszpók megint elrabolta a törpöket Aprajafalvából, és mindegyiket külön cellába zárta. A törpök altatót kaptak, így amikor felébrednek, nem tudják, hogy mennyi ideje vannak fogságban. Minden törp felébred véges idő múlva, de akármennyit alhatnak: lehet, hogy egyikük csak egy napot alszik, másikuk pedig ezer évet. A törpök végtelen sokáig élnek, de nem szeretnék további életüket rabságban tölteni. A törpök az időérzéküket is elveszítették a fogságban, de minden nap ugyanabban az időpontban egyszerre kapnak enni. A cellák ajtaját Hókuszpók varázslata tartja zárva, ami egyetlen módon törhető csak meg: ha a törpök ugyanabban az időpontban mind egyszerre arra a számra gondolnak, ahányan rabságban vannak tartva a varázslat által.

A törpök nem tudnak egymással kommunikálni, és nem tudják sem azt, hogy Hókuszpók hányukat rabolta el, sem azt, hogy mindenki felébredt-e már. Előzetesen viszont megbeszélhettek bármilyen stratégiát, és már akkor tudták, hogy mindig ugyanabban az időpontban egyszerre kapnak majd enni, és hogy mivel lehet megtörni a varázslatot. Van olyan módszer, amivel meg tudnak menekülni?

Csak 100¹⁰⁰ nap, de megoldható!

Aprajafalván 100-an laknak, ezért számozzák meg magukat a törpök 1-től 100-ig. Az 1-es sorszámú törp, miután fölkel, az első evésnél gondoljon az 1-es számra, a második nap gondoljon a 2-es számra, és így tovább 1-től 100-ig egyesével, majd a 100. nap után kezdje elölről a számolást.

A második törp, miután felkel, gondoljon 100 napon keresztül az 1-es számra, majd a következő 100 napban a 2-es számra, és így tovább, majd kezdje 100·100, azaz 10 000 nap múlva az egészet elölről. Ilyen módon, ha mindketten el vannak rabolva és már mindketten felkeltek, akkor addig, amíg a 2-es számú törp egy adott számot ismételget, az 1-es törp végigmondja az összes számot 1-től 100-ig, azaz valamikor lesz egyezés, és ez az egyezés 10 000 naponként ismétlődni fog, ha mindketten ciklikusan ismételgetik magukat.

A harmadik törp 100·100 napon keresztül gondoljon ugyanarra a számra, a következő 100·100 napban a következőre, és így tovább, vagyis 100·100·100 nap múlva kezdi elölről az egészet. Ilyen módon, ha mindhárman el vannak rabolva és már mindhárman felkeltek, akkor addig, amíg a 3-as számú törp egy adott számot ismételget 10 000-szer, a 2-es törp végigmondja az összes számot 1-től 100-ig, de mindegyiket 100-szor ismételve, ezért lesz vele 100 egyezés, és ebből a 100-ból lesz egy olyan, ami egyezik még a legelső törppel is.

Általában véve amikor az i törp felkel, kezdje az 1-es számmal, majd 100^(i-1) napig ismételgesse, aztán váltson a következő számra, amit szintén ismételgessen 100^(i-1) napig, és amikor minden számot mondott már 100^(i-1)-szer, akkor kezdje a ciklust elölről. Ha így tesznek, akkor legrosszabb esetben – amikor is mind a 100 törp fogságba esett – a legutolsó törp felébredése után 100^100 nappal biztosan kiszabadulnak. Ennek bizonyítása csupán annak a gondolatmenetnek az általánosítása, amelyet a 2-es és 3-as törpnél már leírtunk. Az, hogy valamely törpöt közülük el sem rabolta Hókuszpók, egyáltalán nem befolyásolja a sikerességet.

A prímek mindig segítenek, azaz egy második megoldás

Hasonlóan sok napig tarthat Dömők Dávid olvasónk megoldása, amelyben megint a prímszámokat hívjuk segítségül, ahogy azt az előző törpös feladványnál is tettük, és érdekes módon megint a kínai maradéktétel fog előkerülni. Ehhez minden törp válasszon magának egy 100-nál nagyobb prímszámot úgy, hogy semelyik két törp ne válassza ugyanazt a prímet. Ha minél kisebb prímszámokat szeretnének Aprajafalva lakói választani, akkor ezt 700 alatti számokkal meg tudják oldani, lásd a prímek listáját. A továbbiakban jelöljük az i törp választott prímszámát p(i)-vel.

A törpöknek a következőt kell tenniük. Amikor felébrednek, először mindenki gondoljon az 1-es számra. Ha csak egy törp van fogságban, így ő azonnal kiszabadul. Egyébiránt mindenki gondoljon a következő napon mindig 1-el nagyobbat, azaz számoljon egyesével, de miután elérkezik (p(i)+1)-ig, másnap mindig kezdje újra a számolást 2-től. Ilyen módon 1-re mindenki csak egyszer gondol, de minden más X szám esetében igaz, hogyha egy törp X-re gondol valsmikor, akkor p(i) nap múlva újra X-re fog gondolni.

Legyen az elrablástól számított idő t, ami egy változó mennyiség. Mindent napokban számítunk. A fentiek alapján minden törphöz lesz egy c(i) szám, amire igaz az, hogy amikor a t idő p(i)-vel vett osztási maradéka c(i), akkor az i törp éppen N-re gondol, ahol N az elrabolt törpök száma. Ez a bonyolultnak hangzó kijelentés csak azt fejezi ki, hogy az i törp p(i) naponta gondol az N számra. Ha minden törpre felírjuk, hogy mikor gondol N-re, akkor matematikus jelölést használva így írhatjuk: t ≡ c(i) mod p(i), ahol a ≡ jel a kongurencia jele, ami annyit fejez csupán ki, hogy t és c(i) osztási maradéka ugyanaz, ha p(i)-vel akarunk osztani. A kínai maradéktétel pedig azt állítja, hogyha p(i)-k relatív prímek (ami prímekre teljesül), akkor a kongurencia rendszer megoldható, vagyis lesz olyan t, amikor minden törp N-re gondol.

A legelső megoldó és a megoldásokért kiosztott banánok megtalálhatók a Dicsőségfalon!

Kapcsolódó cikk a Qubiten: