Więźniowie i strażnik
: 6 sty 2018, o 01:25
autor: Hydra147
Mam nadzieję poprawne rozwiązanie:
Ukryta treść:
Podobnie jak w poprzednich próbach rozwiązania oznaczmy pola szachownicy liczbami od 0 do 63.
Rozważmy jednak XOR wszystkich miejsc, na których stoją orły, niech będzie to \(\displaystyle{ k}\). Z racji że XOR liczb mniejszych niż potęga dwójki też jest mniejszy niż ta potęga to \(\displaystyle{ k<64}\) zatem odpowiada mu pole na szachownicy. Jeśli teraz strażnik obrócił monetę na polu \(\displaystyle{ l}\), to XOR zmienił się na \(\displaystyle{ k \otimes l}\). No ale teraz wystarczy, że obrócimy monetę z numerem \(\displaystyle{ k}\) i XOR zmieni się na \(\displaystyle{ (k \otimes l) \otimes k=l}\) więc drugi więzień po przyjściu również policzy ów XOR i odkryje numer monety obróconej przez strażnika.
Co ciekawe, zadanie działa również wtedy, jeśli kolejność jest dokładnie odwrotna - to znaczy najpierw więzień obraca monetę, a dopiero potem strażnik.
Rozważmy jednak XOR wszystkich miejsc, na których stoją orły, niech będzie to \(\displaystyle{ k}\). Z racji że XOR liczb mniejszych niż potęga dwójki też jest mniejszy niż ta potęga to \(\displaystyle{ k<64}\) zatem odpowiada mu pole na szachownicy. Jeśli teraz strażnik obrócił monetę na polu \(\displaystyle{ l}\), to XOR zmienił się na \(\displaystyle{ k \otimes l}\). No ale teraz wystarczy, że obrócimy monetę z numerem \(\displaystyle{ k}\) i XOR zmieni się na \(\displaystyle{ (k \otimes l) \otimes k=l}\) więc drugi więzień po przyjściu również policzy ów XOR i odkryje numer monety obróconej przez strażnika.
Co ciekawe, zadanie działa również wtedy, jeśli kolejność jest dokładnie odwrotna - to znaczy najpierw więzień obraca monetę, a dopiero potem strażnik.