Więźniowie i strażnik

[blade]

Zasłyszałem ciekawą zagadkę, rozwiązanie trochę mi zajęło, więc pomyślałem, że się tutaj nią podzielę:)
W celi jest dwóch więźniów. Strażnik zaproponował, że wypuści ich jeśli dobrze wykonają zadanie, które brzmi następująco :
Do pomieszczenia ze strażnikiem wchodzi jeden z więźniów, na szachownicy (8x8) losowo zostały rozłożone monety (orłem lub reszką). Strażnik obraca na drugą stronę jedną z monet. Zadaniem pierwszego więźnia jest odwrócenie (może również nic nie robić, jeśli nie potrzebuje) jednej z monet, tak aby drugi więzień po wejściu mógł wskazać, która z monet została odwrócona przez strażnika (żeby była jasność więźniowie mogą się ze sobą dogadać co do sposobu itp.).
Zagadka oczywiście brzmi : Jak powinni postępować więźniowie?

[Kartezjusz]

Więzień widzi obrót monety przez strażnika?
S

[blade]

Tak, w tym rzecz, że pierwszy więzień musi przekazać za pomocą obrotu jednej monety, informacje na temat tego, która moneta została odwrócona przez strażnika.

[kerajs]

Może tak:

Pierwszy więzień odwraca monetę na polu A1 (choć lepiej by to było mniej oczywiste pole np. C7).
Jej położenie na polu określa literę pola monety strażnika:
A - blisko górnego boku kwadratu A1
B - blisko górnego oraz prawego boku kwadratu A1
C - blisko prawego boku kwadratu A1
itd.
Obrót monety określa cyfrę pola monety strażnika:
1 - moneta leży normalnie
2 - jest obrócona w prawo o 45 stopni
3 - jest obrócona w prawo o 90 stopni
itd.

Np. moneta blisko lewego boku pola A1 i obrócona o 180 stopni wskazuje na obrócenie przez strażnika monety z pola G5 .

Ps. Można by w ten sposób parę osób naciągnąć na piwo.

[Kartezjusz]

Skąd wiesz, że monety są na tyle małe, żeby różnie ustawić je na polu?

[kerajs]

Jak są większe to tym lepiej, sztuczka jest mniej oczywista.
A - moneta dotyka tylko górnego boku kwadratu A1
B - moneta dotyka górnego oraz prawego boku kwadratu A1
C - moneta dotyka tylko prawego boku kwadratu A1
itd

[blade]

kerajs, zagadka ma polegać na bardziej matematycznym rozwiązaniu, po prostu odwrócenie jednej monety, przy założeniu, że strażnik po wszystkim czyści całą szachownicę i ustawia monety tak jak były ułożone (orłem lub reszką) po zmianie dokonanej przez pierwszego więźnia ^^.

WSKAZÓWKA:    

modulo

[Kartezjusz]

Ukryta treść:    

pomysł jest taki, aby zakodować za pomocą monet na szachownicy lub jej fragmencie liczbę od 1 do 64. Problem polega na tym, że nie mamy pewności czy ustawienie monet pozwoli na zakodowanie tej liczby jednym ruchem. Kodowań mamy sporo. Na przykład systemem dwójkowym. Orły 1 reszki 0 i ewentualnie mod 64 jeśli tych wartości kodu jest powyżej 64. We szystkich sytuacjach jednak nadziewałem się na to czy jednym ruchem monety niezależnie od ustawienia początkowego jestem zakodować dowolne pole.

[blade]

Rozwiązanie jest bardzo proste, jeśli chcesz to mogę napisać, ale nie chcę psuć Tobie zagadki

[Kartezjusz]

Upomnę się później o wskazówkę-- 5 listopada 2015, 18:21 --Malutka zajawka? Każdy sposób jest kontrowany ustawieniem monet na szachownicy.

[blade]

Przepraszam Kartezjusz, nie zajrzałem tutaj odkąd edytowałeś post, dopiero teraz kerajs przypomniał mi o tym wątku.

Hm.. Wskazówka? Myślę, że druga wskazówka z poniższych mocno wyjaśnia sprawę.

WSKAZÓWKA 1:    

Przypuśćmy, że strażnik odwraca n-te pole.
Co pierwszy więzień może zrobić z orłami lub reszkami w modulo 64?

WSKAZÓWKA 2:    

Jeżeli pierwszy więzień zliczy sobie np. orły w modulo 64 (przypuśćmy, że numer pola=numer monety), to co musi zrobić, aby dać drugiemu więźniowi informację o polu strażnika?

[Rafsaf]

Może tak:

Ukryta treść:    

Numerujemy szachownicę od \(\displaystyle{ 1}\) do \(\displaystyle{ 64}\), każde pole ma więc wartość numerka, które przyjęło.

Niech strażnik odwróci monetę na polu o numerku \(\displaystyle{ n}\), wydaję mi się, że to bez znaczenia czy z reszki na orła czy na odwrót.
Np. więźniowie dogadali się, że będą tylko na orłach operować, reszki ich nie obchodzą.

Liczymy sumę wszystkich pól orłów. Oznaczmy ją jako \(\displaystyle{ s_{1}}\). Mamy wtedy przystawanie:

\(\displaystyle{ s_{1} \equiv x \pmod{64}}\)

Oczywiście \(\displaystyle{ x}\) przyjmuje wartości z zakresu \(\displaystyle{ \left\langle 0,1,2,...,63\right\rangle}\)
I teraz dobieramy taką liczbę \(\displaystyle{ y}\) aby \(\displaystyle{ n=x-y \vee n=x+y}\), odwracamy pole \(\displaystyle{ y}\)(aby dodać lub odjąć, zależy jaki układ mamy),
zmienia się suma orłów na jakąś \(\displaystyle{ s_{2}}\)


Wówczas jak policzymy orły , to mamy
\(\displaystyle{ s_{2} \equiv n \pmod{64}}\) Więc ten drugi jak sb policzy, to wie że ta reszta ma wartość pola strażnika.

Gorzej jak się zapomni i zacznie liczyć reszki, albo pomyli się w dodawaniu, wtedy kapput

Jeśli coś pokręciłem, proszę o wyrozumiałość.

[blade]

Dokładnie tak, weź rozwiązanie w hide, /hide, aby ukryć, może ktoś będzie chciał sam dojść do rozwiązania

[Rafsaf]

Przyznam, że bez wskazówki 2 nic bym nie wskórał. Ciekawa zagadka.

[Dasio11]

To rozwiązanie jest niedobre. Załóżmy, że początkowo orły leżą na polach \(\displaystyle{ 4}\) i \(\displaystyle{ 8}\) a strażnik odwraca monetę na polu \(\displaystyle{ 8}\) reszką. Wtedy \(\displaystyle{ s_1 = 4,}\) więc \(\displaystyle{ y = 4 \vee y = 60.}\) Jednak obrócenie każdej z tych dwóch monet zmieni sumę na \(\displaystyle{ 0}\) a nie \(\displaystyle{ 8,}\) tak jak chcemy.