Feladat: A.760 Korcsoport: 18- Nehézségi fok: nehéz
Kitűző(k):  Nikolai Beluhov (Bulgária) ,  Palmer Mebane (USA) 
Füzet: 2019/október, 418. oldal  PDF  |  MathML 
Témakör(ök): Nehéz feladat, Logikai feladatok, Játékelmélet, játékok

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 k egy pozitív egész. Egy néző n=k!+k-1 darab golyót kap, melyek az 1,2,...,n 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 k 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 n 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.)