Fyra glas problem

The Four Glasses Problem [1] är ett logiskt pussel av Martin Gardner . Publicerad i kolumnen "Math Games" i februarinumret 1979 av Scientific American .

Formulering

Fyra glas finns i hörnen på ett fyrkantigt vridbart bord. Vissa glasögon är uppsatta (dvs. korrekt), och andra är nervända (dvs. upp och ner). En person med ögonbindel måste ordna om glasögonen så att alla är i samma position, i så fall ringer klockan. Glasen kan arrangeras om ett och ett enligt följande regler. Vilka två koppar som helst kan kontrolleras i ett drag, och genom att känna av deras orientering kan en person ändra orienteringen på någon av dem, ingen av eller båda kopparna. Efter varje rotation roterar bordet med en slumpmässig vinkel. Utmaningen är att utveckla en algoritm som gör att en person med ögonbindel kan verifiera att alla glasögon har samma orientering (upp eller ner) i ett ändligt antal rotationer. Algoritmen måste vara icke-stokastisk, det vill säga den får inte bero på tur. [2]

Lösning

Algoritmen som garanterar att klockan ringer efter högst fem varv är följande: [3]

  1. Vid första varvet, välj det motsatta paret glasögon diagonalt och vänd båda glasögonen upp och ner.
  2. På den andra svängen väljer du två intilliggande glas. Minst en av dem reser sig som ett resultat av föregående steg. Om den andra är nere, vänd den också. Om klockan inte ringer, så är nu tre glas uppe och ett är nere.
  3. Vid tredje varvet väljer du det motsatta glasögonen diagonalt. Om en av dem är nere, vänd på den och klockan ringer. Om båda är uppe, vänd en. Nu ställs två glas ner, och de står sida vid sida.
  4. På fjärde varvet, välj två intilliggande glas och vänd båda. Om båda var i samma riktning skulle klockan ringa. Annars är nu de två glasen upp och ner och de ska vara diagonalt isär från varandra.
  5. Vid det femte varvet, välj det motsatta paret glasögon diagonalt och vänd båda. Klockan kommer att ringa.

Generaliseringar

Pusslet kan generaliseras till n glas istället för fyra. För två glas löses detta trivialt i ett drag genom att vända på något av glasen. För tre glas finns en algoritm i två varv. För fem eller fler glas finns det ingen algoritm som garanterar att klockan ringer i ett ändligt antal varv. [fyra]

En ytterligare generalisering gör att du kan kontrollera k koppar (istället för två) av n koppar vid varje varv. Det är möjligt att hitta en algoritm som löser problemet i ett ändligt antal varv om k ≥ (1 − 1/ p ) n , där p är den största primfaktorn för n . [fyra]

Anteckningar

  1. ↑ Ehrenborg, Richard (1995). "Den blinde bartenderns problem" (PDF) . Journal of Combinatorial Theory, serie A. 70 (2): 249&ndash, 266. DOI : 10.1016/0097-3165(95)90092-6 . Arkiverad (PDF) från originalet 2021-08-13 . Hämtad 2021-11-14 . Utfasad parameter används |deadlink=( hjälp )
  2. ↑ Braingle » Brain Teaser "Fyra exponeringsglas" . Hämtad 14 november 2021. Arkiverad från originalet 14 november 2021.
  3. ↑ Havil, Julian. Kapitel 4: The Spin of a Table // Nonplussed! . - Princeton University Press, 2007. - ISBN 978-0-691-12056-0 . Havil, Julian (2007). "Kapitel 4: Ett bords snurrande".
  4. ↑ 1 2 Havil, Julian. Kapitel 4: The Spin of a Table // Nonplussed! . - Princeton University Press, 2007. - ISBN 978-0-691-12056-0 . Havil, Julian (2007). "Kapitel 4: Ett bords snurrande". upprörd! . Princeton University Press. ISBN 978-0-691-12056-0.