Mynten på schackbrädet


Rekommenderad från: 15 år

Du sitter i en fängelsehåla och en vakt kommer till dig med ett erbjudande. Han säger att han kommer lägga upp mynt (totalt 64 st.) på ett schackbräde, ett mynt i varje ruta och det kommer vara slumpat för varje mynt huruvida det ligger med krona eller klave uppåt. Därefter kommer vakten peka på en ruta. Du får sedan en möjlighet att vända upp-och-ner på exakt ett av mynten, vilket du vill.

Därefter kommer en kompis in i rummet, som får se schackbrädet och får gissa vilken ruta vakten pekade på. Gissar han rätt, får ni båda gå fria. Hur kan du och kompisen komma överens om en strategi som garanterar er frihet, oavsett hur vakten gör?

The_Chess_Board

Visa lösningen

9 reaktioner till “Mynten på schackbrädet”

  1. Vad händer om schackbrädets sida/sidor inte är en 2-potens? Kan man fortfarande lösa problemet?

  2. Hej! Vad jag ser så är det inte möjligt. Oavsett storleken på brädet har vi precis så många alternativ till vändning så att det räcker att särskilja på mynten, det vill säga vi kan inte slösa med information. På grund av symmetri borde lika många utseenden på brädet (dvs upplägg av mynt) ha samma värde för varje värde. Men antalet utseenden på brädet är en tvåpotens, medan antalet värden är inte det, motsägelse.

  3. Hmm, inte helt säker på att jag hänger med på ditt argument.
    På det rätt enkla fallet då vi har ett 3×1 bräde (1×1 är ju en tvåpotens…) så går det att lösa, min regel är helt enkelt att den som det bara finns en av är den vi väljer (med exempelvis XOX väljer vi mitten och med OOX den till höger). Detta går att konstruera oberoende av startsituation.

  4. I fallet 1×3 går det t.ex. inte att fixa ifall det ser ut som XOX från början och vakten pekar på mittenmyntet, eftersom man måste vända på något.

  5. Mitt resonemang tillämpat på 1×3-fallet: Det finns 8 lägen som brädet kan vara i. Det betyder att någon myntposition ska klara sig med högst två lägen. Det vill säga hur vi än har mynten från början ska vi kunna komma till de två lägen. Eftersom grafen över lägen (och övergångar dem emellan) är symmetrisk kan vi välja två lägen åt alla andra mynt också, som kan nås var som helst ifrån (det steget är jag inte helt säker på, men känns intuitivt att det stämmer). Då behöver vi bara 6 lägen. Det betyder att vi någonstans förlorar information, vilket vi inte har råd att göra.

  6. “Du får sedan en möjlighet att vända upp-och-ner på exakt ett av mynten, om du vill. ” Tolkade jag som att det var frivilligt att vända på mynt.
    Om det inte är frivilligt så håller jag jag nog med.

    Det enda intressanta är antalet rutor (så MNx1=MxN rutor), jag antar N rutor.
    Vi kan se en given position (utdelade krona/klave) som en nod i hyperkubsgrafen K={0,1}^N. Vi vill då hitta N disjunkta nodmängder X_i så att varje sådan mängd X_i har egenskapen att för varje given nod g så finns det en granne till g i X_i (dvs genom att “flippa” ett mynt kan vi hitta till en konfiguration som bestämmer rutan i).
    Vi noterar också att varje nod har precis N grannar, så varje granne måste tillhöra någon X_i, alltså måste vi fylla upp vår graf helt (då varje nod måste tillhöra något X_i). Dvs den disjunkta unionen av alla våra X_i är K. Antag att vi har hittat en sådan konfiguration av mängder. Vi ser också att varje nod har precis 1 granne i varje X_i.
    Låt oss ta en sådan mängd X. Vi summerar antalet grannar tillhörande X över varje nod i hyperkuben. Detta blir trivialt 2^N (då varje nod hade exakt en sådan granne). Vi kan också räkna ut summan genom att ta varje nod i X och summera antal grannar den har. Detta blir då |X|*N (då varje nod har exakt N grannar, så speciellt har varje nod i X det). Alltså så har vi |X|*N=2^N.
    Då följer att N|2^N!

  7. Ja, så kan man också göra! Det blev ju nästan lite “Lagrange sats”-känsla över beviset :)

  8. Du har rätt, jag publicerade en gammal formulering av problemet, ska ändra på det. Först var jag nämligen osäker på om man var tvungen att ändra, men sedan utgick jag från att man var tvungen (tänkte att man ändå inte tjänade så mycket på att inte vara tvungen att vända). Men i den svagare versionen vet jag inte vilka N som lösningen existerar för. Skulle gissa att det går för 3, men inte för 5 eller högre.

Kommentera