Puzzle čtyři brýle - Four glasses puzzle - Wikipedia

The čtyři brýle puzzle, také známý jako problém slepého barmana,[1] je logická hádanka, kterou poprvé zveřejnil Martin Gardner ve sloupci "Matematické hry" ve vydání z února 1979 Scientific American.[2]

Hádanka

Na rozích čtverce jsou umístěny čtyři sklenice nebo stavítka Líná Susan. Některé brýle jsou svisle (nahoře) a jiné vzhůru nohama (dolů). Vedle Lazy Susan sedí osoba se zavázanýma očima a je povinna znovu uspořádat brýle tak, aby byly všechny nahoře nebo dole, přičemž každé z těchto uspořádání je přijatelné, což bude signalizováno zazvoněním zvonu. Brýle mohou být uspořádány střídavě podle následujících pravidel. Jakékoli dvě sklenice mohou být zkontrolovány v jedné zatáčce a po pocitu jejich orientace může osoba obrátit orientaci jedné, žádné nebo obou sklenic. Po každém otočení se Lazy Susan otáčí v náhodném úhlu. Hádankou je vymyslet algoritmus, který umožní osobě se zavázanýma očima zajistit, aby všechny brýle měly stejnou orientaci (buď nahoru nebo dolů) v konečném počtu zatáček. Algoritmus musí být nestochastický, tj. Nesmí záviset na štěstí.[3]

Řešení

Algoritmus, který zaručuje, že zvonek zazvoní maximálně v pěti zatáčkách, je následující:[2]

  1. Na první zatáčce vyberte úhlopříčně protilehlé brýle a obě brýle otočte nahoru.
  2. Na druhém kole vyberte dvě sousední sklenice. Alespoň jeden bude v důsledku předchozího kroku nahoru. Pokud je druhá dole, také ji zvedněte. Pokud zvon nezvoní, jsou nyní tři sklenice nahoru a jedna dolů.
  3. Ve třetí zatáčce zvolte úhlopříčně protilehlé brýle. Pokud je někdo dole, zvedněte jej a zazvoní zvonek. Pokud jsou obě nahoru, otočte jednu dolů. Nyní jsou dole dvě sklenice, které musí sousedit.
  4. Ve čtvrté zatáčce vyberte dvě sousední sklenice a obě otočte. Pokud byly obě ve stejné orientaci, zazvoní zvonek. Jinak jsou nyní dole dvě sklenice a musí být šikmo proti sobě.
  5. V páté zatáčce zvolte úhlopříčně protilehlé brýle a obě otočte. Zvonek zazvoní.

Zobecnění

Puzzle lze zobecnit na n brýle místo čtyř. U dvou sklenic je to triviálně řešeno v jedné zatáčce obrácením obou sklenic. U tří brýlí existuje dvouotáčkový algoritmus. U pěti a více brýlí neexistuje žádný algoritmus, který by zaručoval, že zvonek zazvoní v konečném počtu zatáček.[2]

Další zobecnění umožňuje k sklenice (místo dvou) z n brýle, které se mají zkoumat při každém otočení. Algoritmus lze nalézt, aby zazvonil na zvonek v konečném počtu otáček, pokud k ≥ (1 − 1/p)n kde p je největším hlavním faktorem n.[2]

Reference

  1. ^ Ehrenborg, Richard; Skinner, Chris (1995). „Problém slepého barmana“ (PDF). Journal of Combinatorial Theory, Series A. 70 (2): 249–266. doi:10.1016/0097-3165(95)90092-6.
  2. ^ A b C d *Havil, Julian (2007). „Kapitola 4: Točení stolu“. Bez přeplnění!. Princeton University Press. ISBN  978-0-691-12056-0.
  3. ^ http://www.braingle.com/brainteasers/8758/four-glasses.html

http://puzzlersworld.com/interview-puzzles/four-glasses-on-a-square-table/