A strucctojás rendelkezik egy olyan tulajdonsággal, hogy ha azt leejted egy bizonyos magasságból, akkor összetörik, viszont ha e magasság alól ejted le AKÁRHÁNYSZOR, akkor nem. Ezt a magasságot nevezzük határmagasságnak!
Van egy 36 emeletes házunk és 2 egyforma strucctojásunk. A feladat az, hogy találjuk meg melyik 2 emelet között van a határmagasság, legrosszabb esetben is minél kevesebb próbálgatásból (próbálgatás = leejtés). A strucctojások összetörhetnek, de ha mindkettő összetört, akkor vége.
Magyarázat a "legrosszabb esetben is minél kevesebb próbálgatásból" kifejezésre: Ha például az a stratégiád, hogy először ledobod a 2. emeletről, ha nem tört össze a tojás, akkor a 4. emeletről, ha ott sem, akkor a 6-ról ... és mondjuk a 14. emeletnél összetörik, akkor ha ledobod a 13-ról biztos meg tudod állapítani, hogy a határmagasság a 12-13 vagy 13-14 emeletek között van-e. Látható, hogy ennél a stratégiánál a legrosszabb eset az, ha a 35-36 (vagy 34-35) emeletek között van a határmagasság. Ilyenkor 18 próbálgatásra van szükség. A feladat tehát olyan stratégiát találni, ahol ez a szám kisebb. A megoldás akkor teljes, ha belátod nincs ennél jobb stratégia.
56 emeletes a ház és 3 strucctojásunk van.
n emeletes a ház, k db tojásunk van. Az optimális megoldásban a legrosszabb estben szükséges próbálgatás száma i. Mi az összefüggés n,k és i között ?
Úgy hozta a sors, hogy a buta közgazdászok foglyul ejtettek 100 db okos informatikust. Azt mondták nekik: "5 perc múlva libasorba kell állnotok, majd mindegyikőtök fejére felteszünk vagy egy fehér, vagy egy fekete sapkát, azután elindulunk hátulról egyesével előre, és mindenkinek feltesszük a kérdést, hogy: "Na, milyen sapka van rajtad?". Ha eltalálod elengedünk, ha nem lelövünk. A válsz csak annyi lehet, hogy fehér vagy fekete, ellenkező esetben mindenkit megölünk. 5 percetek van tehát"
A feladat tehát minél több okos informatikus megmentése. Tudni kell még, hogy a libasor olyan, hogy mindenki látja az előtte lévők sapkáját, de se sajátját, sem a mögötte lévőkét nem. Az is fontos, hogy az esetleges lövést mindenki hallja, és egyértelműen halált jelent.
Egy megoldás lehet (persze nem a legjobb), hogy minden páratlan sorszámú helyen álló az előtte lévő sapkájának színét kiálltja fel. Ekkor a páros sorszámú helyen állók biztosan megmenekülnek, hiszen hallották, hogy milyen színű sapka van rajta. Tehát ezzel az algoritmussal legrosszabb esetben 50 ember megmenekül.
A feladat jobb taktikát találni!
Az egy osztályon dolgozó emberek mindegyike szeretné megtudni, hogy mennyire keresnek jól a többiekhez képest. Pontosabban szeretnék meghatározni az osztályon dolgozók átlagkeresetét, hogy ebből le tudják szűrni, vajon alul vannak-e fizetve vagy sem.
A feladat egy olyan módszert találni, hogy anélkül, hogy bárki elárulná a keresetének összegét, meg tudjuk határozni az átlagot. Még csak olyan információhoz se lehessen jutni, amiből megtudhatjuk, hogy van olyan ember aki X összeget keres.