A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Egy bűvész és a segédje a következő trükköt hajtja végre. Legyen egy pozitív egész. Egy néző darab golyót kap, melyek az számokkal vannak ellátva. A bűvész szemét bekötik, és a néző sorba rakja a golyókat. A segéd megnézi golyókat, kiválaszt egymás mellett lévő golyót, és letakarja egy kendővel. Ezután a bűvész szeméről leveszik a kötést, aki megnézi a golyók sorozatát, és megmondja a letakart golyók pontos sorrendjét. Adjunk meg egy stratégiát a bűvész és a segédje számára, amely mindig működik. (Egzisztenciabizonyításra csak részpontszám jár. Teljes pontszám konstruktív módszerre adható, amely függvényében polinomiális lépésszámban megadja a módszert. Azt nem kell külön indokolni, hogy a megadott konstruktív módszer polinomiális lépésszámmal fut.) |