Hókuszpók és a törpök című feladványunkban Hókuszpók N törpöt elrabolt Aprajafalvából, ahol 100 törp lakik, és mindegyiket külön cellába zárta. Hókuszpók fel akarja hizlalni a törpöket, ezért sorba látogatja a cellákat egy kosár pogácsával. Minden alkalommal, amikor belép egy cellába, az ott lévő törpnek kötelező ennie legalább egy pogácsát, de ehet többet is, legfeljebb pedig annyit, amennyi még a kosárban van. A maradék pogácsákkal Hókuszpók megy a következő cellába, de amikor a kosár kiürül, rögtön újabb adagot süt, és a soron következő cellába már az új adaggal érkezik. Minden adag egyformán M darab pogácsából áll, és a kosárba csak akkor kerülnek új pogácsák, amikor valamelyik törpnél teljesen kiürül. Hókuszpók a cellákat mindig ugyanabban a sorrendben látogatja végig, amikor pedig a cellák végére ér, akkor kezdi újra elölről a körútját a legelső cellával.

A törpök nem tudnak egymással kommunikálni, csak azt látják, hogy Hókuszpók hány pogácsával érkezik hozzájuk. Viszont kezdetben nem tudják sem azt, hogy Hókuszpók hányukat rabolta el, sem azt, hogy ki hányadik cellában van, sem azt, hogy hány pogácsát süt Hókuszpók, amikor újratölti a kosarát, de azt tudják, hogy mindig ugyanannyit, és legalább 15-öt. Előzetesen viszont – a fenti procedúra ismeretében – a törpök megbeszélhettek bármilyen stratégiát. Ha valamikor az egyik törp teljes bizonyossággal meg tudja mondani, hogy pontosan hányukat rabolta el Hókuszpók, akkor mindannyian megmenekülhetnek. Van olyan módszer, amivel meg tudnak menekülni?

Van ilyen módszer, az alábbiakban két különböző metódust ismertetünk. Elsőként Samoránsky János leírását követjük, majd Dr. Vell megoldását mutatjuk be.

Az első alkalommal mindegyik törp egye meg az összes pogácsát a kosárból, így Hókuszpók mindig teli kosárral megy a következő törphöz, és minden törp meg fogja tudni, hogy egy alkalommal hány pogácsát süt Hókuszpók, azaz ismerni fogják M-et.

A második körben legyen a következő a megbeszélt taktika: amelyik törpnél M darab pogácsa van a kosárban, az egye meg majdnem az összeset, csak egyetlen egyet hagyjon a kosárban. A megmaradt pogácsát a következő törpnek meg kell ennie, mást nem tehet. Így felváltva lesz M db illetve 1 db pogácsa a kosárban. Azok a törpök, akiknél M db van, kikövetkeztetik, hogy páratlanadik számú cellában vannak, akiknél pedig 1 db, azok tudni fogják, hogy páros sorszámú cellában vannak.

A harmadik kör – és egyébként minden páratlanadik kör a későbbiekben – legyen egy ugyanolyan nullázó kör, mint a legelső kör, azaz minden törp egye meg az összes pogácsát.

A negyedik körben az a törp, aki M db pogácsát talál a kosárban, egyen meg M-2 pogácsát, aki pedig kevesebbet, az mindig csak egyet egyen. Így attól függően, hogy a harmadik körben hány pogácsával érkezik egy törphöz Hókuszpók, a törp meg tudja állapítani a cellaszám 3-mal való osztási maradékát: aki ugyanis M pogácsát lát, annál 1 a maradék, aki 2-őt, annál 2 a maradék, aki pedig csak 1-et, annál nincs maradék, azaz 3-al osztható a cellája sorszáma.

Teljesen hasonlóan egy későbbi páros sorszámú körben megállapíthatják a törpök a sorszámuk p-vel való osztási maradékát, ha az a törp, aki M db pogácsát talál a kosárban, megeszik (M-p+1)-et, mindenki más pedig 1-et. Mindez addig működik persze, amíg p kisebb M-nél. Azok a nullázó körök pedig, amikor mindenki mindent megeszik, azért szükségesek, hogy a következő kör elején biztosítva legyen, hogy az első cellában lévő törpnél a maximális számú M db pogácsa van, vagyis tényleg a sorszám maradékait számolják.

Ha a törpök p-nek a 2, 3, 5 és 7 számokat választják, akkor a 8. kör végére mindegyik törp tudni fogja a cellaszámának a 2-vel, 3-mal, 5-tel és 7-tel vett osztási maradékát. 1-től 100-ig a számokat viszont egyértelműen meghatározzák a fenti osztási maradékok, sőt a kínai maradéktétel szerint 2·3·5·7 = 210-en is lakhatnának Aprajafalván, akkor is egyértelmű lenne mindenki számára a saját sorszáma, mert prímszámok esetében (sőt elegendő, hogy csak relatív prímek legyenek) a maradéklista (a négy prímmel vett osztási maradék) 210-esével fog csak ismétlődni.

De hogyan fogja ebből valaki megtudni, hogy hányan vannak összesen? Nézzük az első cellában lévő törpöt, aki ugye egy idő után – legkésőbb a 8. körben – meg fogja tudni, hogy ő van az első cellában. Neki kitüntetett szerepe van, mert páratlan (nullázó) körökben az első cellán kívül az összes törp M db pogácsát fog találni, ő viszont látni fogja, hogy az előző (páros) kör legvégén hány pogácsa maradt, vagyis ki fogja tudni találni az utolsó törp sorszámát (ami az összes törp száma), mert lényegében az ő maradékait is végig látja.

Egy másik megoldás, amiben Törpapának kitüntetett szerep jut

Ez a megoldás akárhány pogácsára működik, sőt Hókuszpók süthet összevissza változó mennyiséget, csak az a lényeg, hogy mindig legalább két pogácsát süssön. Az egyszerűség kedvéért tekintsük a feladatnak az alábbi átfogalmazását. Mindenki kap egy bitet, azaz jelet, amely a 0 és 1 értékek valamelyikét veheti fel, és továbbad egy bitet úgy, hogy abban az esetben, ha 1-est kapott, akkor kötelezően 0-át kell továbbadnia. Hogyan kapcsolódik ez a pogácsákhoz? A továbbítandó bit értéke 0, ha egy törp mindent megesz, és 1 az értéke, ha hagy pogácsát, ilyenkor viszont megköveteljük, hogy mindig pontosan egy pogácsát hagyjon. A falu lakossága legyen L, ami a feladat szerint 100, de a megoldás bármekkora L-re működni fog.

Törpapán kívül mindenki csinálja azt, hogy ha 1-et kap, akkor közvetlenül ezután adjon 0-át tovább (ez kötelező is), viszont amikor legközelebb jön, akkor 1-et. Amikor pedig 0-át kapnak, akkor alapból adjanak tovább 0-át (kivételt lásd később). Törpapa viszont adjon 1-et először, utána ő is 0-át. Ily módon a Törpapa által elindított 1-es jel lassan fog terjedni előre, azaz körönként lép egyet tovább. Eközben Törpapa számolja, hogy hány kör telik el, amíg vissza nem kapja a jelet (1-est), ennyi törpe lesz.

De mi van akkor, ha Törpapát nem rabolták el? Ilyenkor L-szer körbemegy a 0, és ezt mindenki látja. Ekkor aktiválja magát Törpilla. Ha tehát Törpilla L+1 db 0-át kap, akkor az a feladata, hogy küldjön egy 1-est. A protokoll többi része ugyanaz. Ha Törpilla sincs elrabolva, akkor mondjuk Okoska indít 1-est 2L+1 darab 0 után. És így tovább, a törpök előzetesen felállítanak egy rangsort a faluban, és a rangsor szerint aktiválódnak, amikor rajtuk a sor.

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

Kapcsolódó cikk a Qubiten: