7 Kart

[Gość: Kriss]

Walczę z następującym zagadnieniem:
Wylosowano 3 osoby, które nigdy wcześniej się nie spotkały: A, B i C. Dostali
talię złożoną z siedmiu kart, np: A K D W 10 9 8 w jednym kolorze - wszyscy
zobaczyli te karty. Następnie takię potasowano i rozłożono osobom A i B po 3
karty, siódmą kartę dostała osoba C. No i teraz problem:
Jakie informacje/pytania/uwagi powinni wymieniać między sobą A i B (otwartym
zrozumiałym dla wszystkich tekstem), żeby ze 100% pewnością poznać wzajemnie
swoje karty, natomiast żeby C ze 100% pewnością nie poznał jakie karty mają A
i B?

[cardemon]

W jednym zdaniu rozwiązanie brzmi: należy kartom przypisać numery od 1 do 7, po
czym gracz A i B podają sumy modulo 3 i modulo 4 swoich kart.
Tłumacząc to na język polski, obaj gracze obliczają sumę swoich kart, dzielą tę
sumę przez 3 i przez 4, po czym podają głośno obie reszty z dzielenia. Dla
gracza A i B są tylko cztery możliwe trójki, jakie może posiadać partner i
informacja o obu resztach z dzielenia wystarczy, by mogli oni wzajemnie
precyzyjnie określić swoje 3 karty. Natomiast niewystarczy ona dla C, by mógł
odgadnąć układy kart A i B.
Bardzo dobra zagadka!

Pozdrawiam,
CdM

[cardemon]

Niestety moje powyższe rozwiązanie nie jest prawidłowe. Wycofuję się z niego.

CdM

Poprawione rozwiązanie

[cardemon]

Z rozwiązania się wycofałem, ale krótko powiem skąd mi się ono wzięło.
Pierwotnie myślałem o modulo 2 i modulo 3, ale zauważyłem, że rozwiązanie nie
będzie jednoznaczne w przypadku dwóch układów, dlatego zmieniłem modulo 2 na
modulo 4. Tym razem jednak okazało się, że o ile rozwiązanie dla A i B jest
jednoznaczne, to C może również w niektórych przypadkach odgadnąć trójki kart
na rękach A i B.
Wracam zatem do mojego pierwszego pomysłu i proponuję następujące rozwiązanie.
Wpierw karty numerowane są liczbami od 1 do 7. Panowie A i B zliczają sumę
swych kart i podają resztę z dzielenia tej sumy przez 2 i przez 3. Informacja
ta pozwoli im by mogli teraz odgadnąć trójki kart u partnera, natomiast nie
wystarczy panu C do odgadnięcia ich kart. Jest od tego jednak drobny wyjątek.
W dwóch przypadkach jeden z graczy nadal nie będzie mógł odgadnąć kart
partnera, a mianowicie gdy będzie miał u siebie układ kart (2,3,4) lub (4,5,6)
i kiedy partner poda swoje reszty z dzielenia jako 0 i 0. Rozpisując to
bardziej szczegółowo, jeśli A posiada układ (2,3,4) to B może mieć (1,5,6) lub
(1,5,7) lub (1,6,7) lub (5,6,7), gdzie reszty z dzielenia przez 2 i 3 wynoszą
odpowiednio [0,0], [1,1], [0,2], [0,0]. Pan A nie ma więc możliwości odróżnić
układów (1,5,6) i (5,6,7). Analogicznie jest gdy A posiada układ (4,5,6). Co w
takim przypadku? W takim przypadku gracz B powinien podać wartość karty na ręku
pana C. Czy C będzie mógł odgadnąć ręce panów A lub B? Nie, bo zarówno układ
(2,3,4) jak i (4,5,6) dają tę samą parę reszt z dzielenia [1,0]. Pan C będzie
jedynie mógł się domyślić jednej karty na ręku pana B (1 lub 7). Żeby to ominąć
można wprowadzić trochę odmienną procedurę odgadywania, a mianowicie:

Panowie A i B zliczają swoje sumy i obaj mówią, czy suma jest parzysta (podział
przez 2). Teraz są trzy przypadki:
1. Obie sumy nieparzyste - panowie mówią jaka jest reszta z dzielenia przez 3 i
odgadują swoje ręce.
2. Obie sumy parzyste - to samo co wyżej, panowie mówią jaka jest reszta z
dzielenia przez 3 i odgadują swoje ręce.
3. Jedna parzysta, druga nieparzysta - pan posiadający nieparzystą mówi, jaka
jest reszta z dzielenia przez 3, na co drugi pan już wie co posiada C i zamiast
mówić o swojej reszcie z dzielenia przez 3 podaje wartość karty na ręku pana C.

Mam nadzieję, że rozwiązanie tym razem jest jużpełne i poprawne. Jeśli ktoś
znalazłby jakiś kontrprzykład to bardzo proszę.

Pozdr. CdM

[Gość: Kriss]

a modulo 7?

[Gość: Kriss]

tylko ponumerowałem karty 0 1 2 3 4 5 6

[cardemon]

Tak jest! Prosto i elegancko. Widzę, że ze swoimi rozwiązaniami kręciłem się
jak pies wokół własnego ogona. :(

pzdr. CdM

[Gość: Kriss]

!!!
a ja nadal męczę siebie i znajomych tym magikiem z kartami - najlepsza zagadka
na forum
pzdr K

[kopperek]

Gość portalu: Kriss napisał(a):

> a modulo 7?

Dopiero teraz znalazłem Twoje rozwiązanie, identyczne z moim z 10 maja, 13:05...
Trzeba przyznać, że ująłeś to nieco bardziej zwięźle:).

pzdr.

[Gość: Kriss]

:-), ale przyznasz że można to wytłumaczyć prościej: od 7 odjąć sumę reszt z
dzielnia (7) i to karta trzeciej osoby

[cardemon]

kopperek napisał:

> Gość portalu: Kriss napisał(a):
>
> > a modulo 7?
>
> Dopiero teraz znalazłem Twoje rozwiązanie, identyczne z moim z 10 maja,
13:05..
> .
> Trzeba przyznać, że ująłeś to nieco bardziej zwięźle:).
>
> pzdr.
>

Lapidarność rozwiązania Krissa i nieubłagana logika rozwiązania Kopperka -
każdy znajdzie coś dla siebie... :)

Pozdrawiam, CdM

[kopperek]

Uwagi wstępne:
1) Zarówno dla A, jak i B wyatarczającą informacją jest oczywiście to, jaką
kartę ma C.
2) Jeśl jedna z (A,B) już wie, może poe prostu podać drugiemu inormację o karcie
C bez kodowania.

Jeśli ponumerujemy karty na przykład od 0 do 6, to wystarczającą inormacją dla B
będzie suma wartości kart na ręce A (możliwe wartości sum: od 3 do 15). Wtedy B
wie, że karta C to: 21-suma_na_ręku_A-suma_na_ręku_B (21 to sumawszystkich 7
kart). W pewnych jednak przypadkach taka informacja podana wprost byłaby
wystarczająca dla C - na przykład: A ma (0,1,2) i podaje sumę 3 - wszystko jest
oczywiste. Podobnie na przykład dla sumy 6, jeśli C ma na ręce 0: wtedy C wie,
że A ma (1,2,3). Liczby takie (wartości sum, dla których jest możliwe, że C od
razu odgadnie) nazwiemy jednoznacznymi.
Jednoznaczne wartości sum to:
a) 3: (0,1,2);
b) 4: (0,1,3);
c) 5: (0,1,4), (0,2,3) - jeśli C ma 1,2,3 lub 4, odgadnie;
d) 6: (0,1,5), (0,2,4), (1,2,3) - jeśli C ma 0,1,2 - odgadnie.
e) 7: (0,1,6), (0,2,5), (0,3,4), (1,2,4): jeśli C ma 0, dogadnie.
Generalnie aby suma nie była (nie była NA PEWNO) jednoznaczna dla C, musi być
ona realizowana przez pewną liczbę układów, przy czym jeśli tych układów jest n,
to żadna liczba nie może występować w n-1 układach - bo jeśli akurat C ma daną
kartę na ręku, zostanie mu dokładnie jeden możliwy układ, a więc odgadnie.
Sumy niejednoznaczne to: 8,9,10,11. Można sprawdzić, szkoda tu miejsca na to.
Sumy 11,12,13,14 i 15 są "symetryczne względem sum 3..7 (suma trzy to układ
(0,1,2), 15 to (4,5,6) itd.), a więc również jednoznaczne.
Jeśli zatem mamy sumę niejednoznaczną, wystarczy jeśli A poda ją B. B wszystko
już wie, podaje A informację, jaką kartę ma C. (Na końcu rozwiązania małą
poprawka dla tego przypadku).
Jeśli A ma na ręku sumę jednoznaczną, oblicza drugą liczbę wg reguły: do sumy S
dodajemy 7 i odejumjemy 7, jedna z tych liczb leży w zakresie możliwych sum
(3..15), druga nie. Tę, ktora leży w tym zakresie, oznaczamy X. A mówi: "Suma
moich kart na ręku wynosi S lub X". Dla B to wystarczająca informacja: oblicza
kartę C wg wzoru 21-sum(A)-sum(B), podstawiając pod sum(A) raz S, raz X. JTylko
jeden z tych wyników, odpowiadający S, będzie leżał w zakresie 0..6 (skoro
różnią się o siedem).
Czy C odgadnie? Popatrzmy:
a) S=3, A mówi "sum(A)=3 lub sum(A)=10". 10 jest niejednoznaczna, tym bardziej
jej alternatywa z 3;
b) S=4 lub 11, A mówi: "sum(A)=4 lub sum(A)=11". Możliwe układy: (0,1,3),
(0,5,6), (1,4,6), (2,3,6), (2,4,5). ) Układów jest pięć, żadna liczba nie
występuje więcej niż trzy razy (szóstka) - zatem dla C zawsze pozostaną co
najmniej 2 możliwości.
c) S=5 lub 12, A mówi: "sum(A)=5 lub sum(A)=12". Układy: (0,1,4), (0,2,3),
(1,5,6), (2,4,6), (3,4,5). Co najmniej dwa ukłądy dla C (jeśli ma na ręku
czwórkę, w pozostałych przypadkach więcej niż dwa).
d)S=6 lub 13, A mówi "sum(A)=6 lub sum(A)=13". Układy: (0,1,5), 0,2,4), (1,2,3),
(3,4,6), (2,5,6). Znów co najmniej 2 układy dla C.
e) S=7 lub 14, A mówi: "sum(A)=7 lub sum(A)=14", układy: (0,1,6), (0,2,5),
(0,3,4), (1,2,4), (3,5,6). Jak wyżej.
f) S=15, a mówi:"sum(A)=8 lub sum(a)=15". 8 samo w sobie jest niejdnoznaczne.

Jeśli S=8, można też powiedzieć to co przy S=15, jeśli S=10, to co przy S=3.

pzdr.