Dwóch skazańców

[smiechowiec]

Dwóch skazańców Adam i Bolek dostaje szanse na uniknięcie egzekucji.
Strażnik objaśnia im warunki zadania przed jakim zostaną postawieni.
Jeden ze skazańców zapisze na dwóch kartkach dwie różne liczby od 1 do 20.
Strażnik ułoży jedną kartkę po prawej stronie stołu, a drugą po lewej
i przykryje je tak, aby zapisane na nich liczby nie były widoczne.
Następnie drugi skazaniec wybierze jedną z kartek i zobaczy jaka liczba jest na niej zapisana.
Jego zadanie polega na powiedzeniu czy druga liczba zapisana na kartce jest mniejsza czy większa.
Jeśli zgadnie zachowa życie, jeśli nie życie zachowa skazaniec zapisujący liczby.
W pierwszej chwili wynik zadania wydawał się być losowy
więc bez protestu Adam zgodził się zapisać liczby.
Jednak po namyślę żałował swojej decyzji, czy słusznie ?
Kto ma większą szansę na przeżycie ?

[Gość: yyy]

Strażnik.

[taria]

Popatrzmy na wszystko od strony Bolka. Kiedy widzi, że na pierwszej karcie jest liczba a, rozsądek nakazuje mu myśleć tak: jest a-1 mniejszych liczb i 20-a większych liczb od tej, którą widzę.
Jeśli więc a<11 to powiem, że druga liczba jest większa, jeśli a>10, powiem, że druga liczba jest mniejsza.

Jakie jest prawdopodobieństwo, że obierając taką strategię Bolek wygra?
Ogólnie, jeśli Adam napisał liczby {m ,w}(gdzie m<w dla klarowności} mamy trzy przypadki:
(*) 0<m<w<11
Niezależnie, co wylosuje Bolek, przy tej strategii odpowie, że zakryta liczba jest większa. Będzie miał rację z prawdopodobieństwem 1/2

(**)10<m<w<20
Analogicznie, tutaj zawsze odpowie, że zakryta jest mniejsza i będzie miał rację "pół-na-pół"

(***) m<11 i w>10
Tutaj strategia zapewnia Bolkowi pewną wygraną.

W momencie w którym Bolek wybiera, liczby m i w są już stałe, zapisane na kartce, szlus. Bolek losuje tylko jedną z nich!


Zauważmy więc, że niezależnie od tego, jakie liczby zapisze Adam, Bolek zawsze ma przynajmniej równe szanse. Jeśli Adam wybierze głupio,(jak w przypadku trzecim) przegra na 100%.

Gdyby Adam był bezmyślnym automatem, losującym pary różnych liczb<20
(jak lottomat)szanse Bolka byłyby:

1*200/380 +(1/2)*180/380 =29/38= ok.76,3%

Ponieważ jednak nie jest, chyba nie ułatwi Bolkowi zadania wybierając liczby z różnych dziesiątek, a wtedy szanse mają równe.

[Gość: taria]

Innymi słowy: Bolek ma strategię, która dla DOWOLNEJ strategii
Adama daje mu przynajmniej 50% szans, że wygra.


Strategia Adama to po prostu wybranie jakiejś pary.
Bolek odkrywając jedną z kart dowiaduje się na temat strategii Adama
TYLKO tego, że w tej strategii występuje liczba a.

Strategią Bolka jest więc ustalenie sobie z góry, jak zareaguje,
widząc każdą spośród 20 możliwych cyfr.
Prawdopodobieństwo jest związane jedynie z wyborem Bolka: prawa czy
lewa kartka, reszta jest już zdeterminowana z góry strategiami obu
graczy.

W oczywisty sposób Adam nie ma takiej strategii, która dla DOWOLNEJ
strategii Bolka daje mu nie mniej niż 50% szans, bo...

dla każdej strategii Adama {m,w} mamy zbiór takich strategii Bolka, w
których na liczbę m Bolek zdecydował odpowiedzieć:druga jest większa,
na w - że druga jest mniejsza i coś na inne liczby.
Strategie z tego zbioru nie muszą być dobre dla innych strategii
Adama (mogą nawet być tak fatalne, że mówią jesli widzisz 1
odpowiedz, że druga jest mniejsza), jednak ze strategią {m,w} poradzą
sobie z prawdopodobieństwem 100%

Dlatego niezależnie od tego, co wybierze Adam, nie zapewni sobie
wygranej z prawdopodobieństwem większym niż 50%, nawet jeśli
przeciwnik będzie działał zupełnie losowo i bezmyślnie, natomiast
niewłaściwy wybór strategii zmniejsza jego szanse na przeżycie

[kornel-1]

Poniżej przedstawiam pewnego rodzaju rozumowanie, ale nie jestem pewien poprawności całości (poza p.1):

1. Zakładając, że Bolek jest osobą myślącą to zachowa na 100% jeśli Adam zapisze na kartkach liczby (1,20); zachowa życie z szansą co najmniej 50%, jeśli Adam zapisze liczby (1,x) lub (x,20) gdzie x= 2...19
Ale Adam też jest osobą myślącą, więc nie użyje tych par liczb.
2. Jeśli Adam użyje liczb (2,x) lub (x,19) gdzie x=3...18 to Bolek zachowa życie z szansą większą niż 50%. Zatem Adam nie użyje takich par.
....
....
3. Jeśli Adam użyje liczb (8,x) lub (x,13) gdzie x=9...12 to Bolek zachowa życie z szansą większą niż 50%. Zatem Adam nie użyje takich par.
4. Jeśli Adam użyje liczb (9,x) lub (x,12) gdzie x=10 lub 11 to Bolek zachowa życie z szansą większą niż 50%. Zatem Adam nie użyje takich par.
5. Jeśli Adam użyje liczb (10,11) to Bolek zachowa życie z szansą większą niż 50%. Zatem Adam nie użyje takich par.
6. Zatem Adam nie może użyć żadnego zestawu liczb; szansa, że Bolek prawidłowo odgadnie jest zawsze większa od 50%.

Kornel
PS. Widzę, że w międzyczasie pojawiła się odpowiedź Tarii, zaraz tam zerknę.

[taria]

Założenie, że którykolwiek ze skazańców jest istotą myśląca jest daleko idące. Dobra strategia to taka, która bierze pod uwagę, że przeciwnik może grać "głupio"

[kornel-1]

Być może łatwiej zanalizować problem zawężając liczby do zbioru {1,2,3,4,5,6} mającego (jeśli się nie mylę) wymagane własności.
A zatem jeszcze raz:
Case 1. Gdy Adam wybierze (1,6) - Bolek wskaże zawsze prawidłowo drugą liczbę. Szansa Adama na przeżycie 0%.
Case 2. Gdy Adam wybierze (1,2), (1,3), (1,4), (1,5) lub (2,6), (3,6),(4,6), (5,6), to:
a) gdy Bolek zobaczy 1 lub 6 (p=50%) - to prawidłowo odgadnie drugą liczbę (100%); jeśli zobaczy liczbę 2,3,4 lub 5 (p=50%) może wskazać liczbę prawidłowo lub nie. Jakie jest prawdopodobieństwo, że wskaże prawidłowo - wrócę do tego za chwilę. W każdym razie jest niezerowe. W sumie dla Case 2. szansa Bolka to ponad 50%
Case 3. Adam wybiera jedną z par: (2,3), (2,4), (2,5), (3,4), (3,5), (4,5). Bolek może zastosować strategię podawania liczby większej, gdy zobaczy 2 lub 3 i mniejszej gdy zobaczy 4 lub 5. Gdyby Adam losowo wybierał jedną parę z podanej piątki, to szansa Bolka wynosi 10/12=83%

Powstaje kwestia, czy skazańcy zachowują się racjonalnie (logicznie). O to trzeba zapytać Śmiechowca. Ale tradycją tego forum jest, iż postacie zagadek są wybitnie inteligentne ;-) Nieraz mieliśmy tu do czynienia z problemami typu "on wie, że ja wiem,że on wie..."

Rozumiem, że Adam i Bolek są konkurencją dla siebie i każdy z nich szuka indywidualnej optymalnej strategii przeżycia.
W poprzednim poście doszedłem do wniosku, że szanse Adama są mniejsze od 50% jeśli będzie "myślał" tak, jak wskazałem. Oznacza to, że Adam NIE MOZĘ użyć pary (1,6) (case 1. i p. 1. z poprz. postu).
Co do kolejnego punktu 2 - już nie jestem pewien. Bo:
Adam może przyjąć strategię podawania wyłącznie pary (1,2). Bolek o tym nie wie. Ale jeśli przyjmie strategię, że widząc 2 wskazuje jako liczbę "większą" na zakrytej kartce - to przeżyje z prawdopodobieństwem tylko 50% (1/2*100% + 1/2*0% = 50%).
Bolek nie wie, jaką strategię zastosuje Adam, lepiej więc, by widząc "2" - losowo podawał liczbę "większą" lub "mniejszą" na zakrytej kartce. Wygra, jeśli Adam zastosował podaną strategię, przegra, jeśli była odmienna. Ale biorąc pod uwagę, że z pary (1,2) może zobaczyć najpierw "1" - Bolek jest wygrany.
Z kolei Adam wiedząc, że na tę strategię Bolek znalazł "sposób", może losowo podawać pary (1,2) i (2,3). I znów, jeśli Bolek ma strategoię podawania liczby "większej", gdy widzi 2 lub 3 to przeżyje z szansą 50% (1/3*100%+1/6*100%+3/6*0%). Bolek powinien więc znów losowo wskazywać zakrytą liczbę jeśli zobaczy 2 lub 3.
Dotąd doszedłem. Wyciągam z tego wszystkiego wniosek, że Bolek powinien losować! (poza przypadkiem, gdy zobaczy skrajną liczbę). Wówczas ma szansę >50%.

Dla mnie to trudna zagadka. Albo niepotrzebnie skomplikowałem :-(

Kornel

[Gość: xxx]

Jeżeli są to logicy to napewno nie wypiszą liczb 1 i 20. Wynika z
tego , że 2 i 19 również nie wypiszą. Tu zawiedzie ich logika i
liczbe 3 i 18 już mogą napisać.Maja więc 16 liczb do wyboru. Po
odkryciu pierwszej kartki z liczbą wybierać będą zbiór wiekszy i
będą mówić np: dla liczby 5 , że druga jest większa. Dla liczby 8 ,
że druga jest większa a dla liczby 11 , że druga liczba jest
mniejsza. Pierwiastek ósmego stopnia z iloczynu ułamków P
14/15x13/15x12/15x11/15x10/15x9/15x8/15x7/15 daje prawdopodobieństwo
sukcesu O,682799.

[taria]

Nieprawda.
> Jeżeli są to logicy to napewno nie wypiszą liczb 1 i 20.

Dlaczego inteligentny Adam nie napisałby pary liczb 1 i 2?
Jeśli zakładasz, że Bolek ma schemat odpowiadania "wybieramy większy zbiór", to z prawdopodobieństwem 1/2 Bolek przegra.
(Oczywiście, Bolek może też mieć schemat mówiący: widzisz 2 ,mów że na drugiej karcie jest jedynka, ale to nie jest mądry schemat, bo dla większości wybranych przez Adama par go zawiedzie)

Adam nie napisałby pary {1,2} tylko wtedy, gdyby jakaś inna para dawała mu większą szansę wygranej.

Jak już pisałam, przy strategii Bolka "wybieramy większy zbiór" każda
para z dwóch różnych połówek jest przegrana, a dla pary obu liczb mniejszych niż 11 ( czy obu większych od 10 )Bolek ma dokładnie 1/2 szans że wybierze właściwą kartkę.

Czyli: przy strategii Bolka "wybieramy większy" Adam ma szanse co najwyżej 1/2 i napisanie jedynki i innej liczby (byle max 10) nie zmniejsza jego szans.

> Pierwiastek ósmego stopnia z iloczynu ułamków P
> 14/15x13/15x12/15x11/15x10/15x9/15x8/15x7/15 daje
> prawdopodobieństwo sukcesu O,682799.

A tu już kompletnie nic nie rozumiem. Po matematycznemu: jaka jest przestrzeń zdarzeń w twoim modelu? Po polsku: z czego losujesz i jakie zdarzenie uważasz za wygraną.

Moja interpretacja zakłada to, że skazańcy mają z góry ustaloną strategię działania: Adam - że pisze konkretną parę liczb, Bolek - że wie jak zareaguje widząc na kartce poszczególne liczby. Odbywa się losowanie: lewa kartka czy prawa i na podstawie tych strategii wiem, kto wygrał.
Np: Adam pisze liczby {6, 9} Bolek decyduje, że jak zobaczy liczbę parzystą, to powie, że druga liczba jest mniejsza, gdy nieparzysta - że większa. Bolek losuje. Przestrzeń zdarzeń składa się z dwóch elementów: <Bolek wylosował 6> <bolek wylosował 9>. W obu przypadkach Bolek przegrywa. Przy tych strategiach Bolek nie ma szans.

Rzecz w tym, że nie losujemy ani strategii Adama, ani Bolka. To są przemyślane decyzje ludzi. Losujemy tylko kartki, a ludzie muszą zadbać o to, żeby losowanie wyszło jak najlepiej dla nich.

Moje twierdzenie:
(*) jeśli Bolek przyjmie strategię "większego zbioru", to niezależnie jaka była strategia Adama, ma co najmniej 50% (czyli albo 1/2, albo 1) szans w losowaniu.

(**) żadna strategia Adama nie jest przyzwoita, czyli żadna strategia nie daje mu przynajmniej równych szans w przypadku KAŻDEJ strategii Bolka (bo dla konkretnej pary liczb jest 2^8 strategii Bolka w których Bolek wygra na pewno)

[Gość: xxx]

Odkrywamy kartkę a tam liczba 6.Od szóstki do osiemnastki jest 12
liczb natomiast od szóstki do trójki są 3 liczby.Wybieram zbiór
większy i mawiam, że nastepna liczba jest większa.Prawdopodobieństwo
trafienia mam P=12/15. I tak dla każdej liczby. Pierwiastek ósmego
stopnia z tego iloczynu daje mniejsze szanse na przeżycie temu który
pisze liczby.

[Gość: taria]

Nie.
Bo to nie jest tak, że ta druga liczba jest losowana ze zbioru {1..20}.
Ona została już ustalona, kiedy Adam ją zapisywał.

Ale idźmy Twoim tokiem rozumowania

Jesteś Bolkiem. Nie wiesz, jakie liczby zapisał Adam. Postanawiasz, że jeśli zobaczysz 1, 2, 3... 10 powiesz większy, jesli zobaczysz 11..20 - mniejszy.
Par, które mógł wypisać Adam, ustawionych w kolejności(<liczba, którą wylosowałeś>, <druga liczba>) jest 380. To jest Twoja przestrzeń zdarzeń.
Dzieli się ona na rozłączne podzbiory. Jeśli wylosowałeś 6, wiesz, że jesteś w podzbiorze {(6,1)...(6,5),(6,7)..(6,20)} Jeśli działasz zgodnie z Twoim algorytmem, wygrasz z prawdopodobieństwem 14/19.

Jeśli Adam wypisał liczby ZUPEŁNIE losowo, to szansa na to, że wylosowałeś 6 jest 1/20

Z wałkowanego w liceum wzoru na prawdopodobieństwo całkowite, (popularne "drzewka")
prawdopodobieństwo, że jeśli Adam pisze losowo to wygrasz jest więc równe:
<wylosowałeś 1> lub <wylosowales 2> lub ... <wylosowales 20>

1/20 * 19/19 + 1/20 * 18/19 +...+ 1/20 * 14/19 +..+ 1/20 * 10/19 + 1/20 * 10/19 +...+ 1/10 * 19/19 =1/20 * 290/19 = 290/380

Pierwiastków w tym nie ma :)

Nawet przy Twoim założeniu, że wiesz, że Adam nie napisze ani 1, ani 2, ani 19, ani 20, ale poza tym cokolwiek losowo, powyższe obliczenia przepisują się do
1/16 * 15/15 +...+ 1/16 * 8/15 + 1/16 * 8/15 +...+ 1/16 * 15/15 =
184/240

Zadnych pierwiastków ósmego stopnia, zdecydowanie :P

[Gość: xxx]

kaniam się

[Gość: taria]

Aaaaa... już chyba załapałam skąd ten idiotyczny pierwiastek:
ty liczysz ŚREDNIĄ GEOMETRYCZNĄ z prawdopodobieństw niezależnych
zdarzeń :D

No, boskie!

[Gość: xxx]

kłaniam się

Dowcipny Adam ;-)

[kornel-1]

smiechowiec napisał:
> Jeden ze skazańców zapisze na dwóch kartkach dwie różne liczby od 1 do 20.

Dowcipny Adam zapisze na kartkach dwie liczby 19.3 oraz 19.6

Niech se Bolek myśli :-p

Kornel

[smiechowiec]

Taria podała prawidłowy wniosek tzn nie jest znana strategia podania
liczb przez Adama, która zapewni mu prawdopodobieństwo przeżycia
większe nie 0.5, w związku z tym Bolek jest w nieco lepszej sytuacji,
prawie wszystko zależy więc od dobrej strategii Bolka.

kornel-1 napisał:
> Dowcipny Adam zapisze na kartkach dwie liczby 19.3 oraz 19.6
Chodzi o liczby naturalne.

Skazańcy są bardzo inteligentni, spróbujmy postawić się na miejscu
jednego z nich i podać optymalny przepis na przeżycie.
Dla uproszczenia proponuję najpierw rozważyć ciekawy moim zdaniem przypadek dla liczb 1,2,3 i 4.

[taria]

Przypadek 1..4 w zasadzie sprowadza się do tego, że Adam walczy o
przynajmniej równe szanse, a Bolek o pewność wyeliminowania Adama.
Dlaczego? Zobaczmy.

Ponieważ gra jest jednorazowa, możemy założyć, że już przed grą każdy
gracz ustalił sobie strategię.
Strategią gracza A jest para liczb naturalnych (a, b) gdzie ,0<a<b<5
strategią gracza B jest tabelka (funkcja) T która każdej zobaczonej
liczbie naturalnej przyporządkowuje odpowiedź <m> lub <w>

Ponieważ mamy do czynienia z inteligentnymi graczami, z rozważań
możemy wyłączyć te strategie, które DLA KAŻDEJ logicznie
niesprzecznej strategii przeciwnika dają w losowaniu szansę wygranej
poniżej 50%.

Tzn. dla B wyrzucamy wszystkie tabelki, w których T(1)=<m> lub
T(4)=<w>.
Mamy więc cztery nieidiotyczne strategie gracza B.
Oznaczmy je po kolei
T1={<w>,<w>,<w>,<m>} {wierzę, że jest 4}
T2={<w>,<m>,<w>,<m>} {wierzę, że nie ma (2,3)}
T3={<w>,<w>,<m>,<m>} (wierzę, że jest (2,3)
T4={<w>,<m>,<m>,<m>} {wierzę, że jest 1}



Analogicznie dla A wyrzucamy tylko (1,4), bo niezależnie co wylosuje
B, WIE NA PEWNO, jaka ( większa czy mniejsza)jest druga liczba.

Pary (1, 2) nie wyrzucamy, bo przy strategii T1 i T3 jest 50% szans
że A wygra.

Nazwijmy nieidiotyczne strategie gracza A następująco:
A1=(1,2)
A2=(1,3)
A3=(2,3)
A4=(2,4)
A5=(3,4)

Zobaczmy, jak każda z tych strategii radzi sobie z każdą inną.
Mamy tabelkę w której a oznacza, że wygra A , b, że B, a r, że o
wygranej zdecyduje, która karta jest odkryta jako pierwsza.
T1 T2 T3 T4
A1 r b r b
A2 r r b b
A3 r a b r
A4 b r b r
A5 b b r r

To że Adam jest w gorszej pozycji widać na pierwszy rzut oka.

No ale popatrzmy, jak to śmiesznie wygląda: najlepsza strategia Adama
(gdyby Bolek bezmyślnie wybierał nieidiotyczną strategię) to napisać
liczby 2 i 3.
Jednak, jeśli Bolek przypuszcza, że Adam napisze A3=(2,3), sam
podziała wg strategii T3 i wygra.

Ale skoro Adam sądzi, że Bolek działa wg strategii T3, napisze parę
A1 albo parę A5, żeby dać sobie przynajmniej 50% szans w losowaniu.

Za to jeśli Bolek myśli, że Adam napisze właśnie A1 lub A5, powinien
stosować strategię T2, wtedy wygra na pewno.

W końcu gdyby Bolek zdecydował, że stosuje strategię T2, to Adam ze
swoją strategią A3 pokona go na pewno :D Tu kółko się zamyka.

[smiechowiec]

taria napisała:
> W końcu gdyby Bolek zdecydował, że stosuje strategię T2, to Adam ze
> swoją strategią A3 pokona go na pewno :D Tu kółko się zamyka.

Rozumowanie oczywiście jest poprawne, ale proszę powiedz jaki jest
wniosek.

Załóżmy że jesteś w roli Adama, jaką strategię przyjmiesz, aby
zmaksymalizować Twoje szanse przetrwania.
Czyli która para jest lepsza, środkowa (2,3) czy połówkowa (1,2) ?

Bolek wie, że Adam przyjmie najlepszą strategię, zachowa się więc
tak, aby zoptymalizować swoje szanse na przeżycie.
Jakie szanse na przeżycie ma w związku z tym Adam ?

Czy rzeczywiście Bolek jest w lepszej sytuacji ?
Jaką strategię przyjęła byś na miejscu Bolka ?

Miłego weekendu

[taria]

> Załóżmy że jesteś w roli Adama, jaką strategię przyjmiesz, aby
> zmaksymalizować Twoje szanse przetrwania.
> Czyli która para jest lepsza, środkowa (2,3) czy połówkowa (1,2) ?
>
> Bolek wie, że Adam przyjmie najlepszą strategię, zachowa się więc
> tak, aby zoptymalizować swoje szanse na przeżycie.
> Jakie szanse na przeżycie ma w związku z tym Adam ?
>
> Czy rzeczywiście Bolek jest w lepszej sytuacji ?
> Jaką strategię przyjęła byś na miejscu Bolka ?
>
> Miłego weekendu

Ja osobiście ze względu na wrodzoną złośliwość, wybrałabym wariant (1,2), w nadziei na to, że Bolek wcale nie jest zbyt dobrym logikiem i widząc 2 zakrzyknie "ha, przecież nie może być jedynki!", jak któryś z internautów z tego wątku :D

A na poważnie: uważam, że każda ze strategii A1, A3 i A5 jest równie dobra.

Zacznijmy tak: dla Bolka najgorszą strategią jest oczywiście strategia T2. Jest jedyną, która ma kontrstrategię wygrywającą(A3), a dla kontrstrategii A1, A2, A4 i A5 inne strategie radzą sobie nie gorzej niż T2.

Tak więc na miejscu Bolka nie wybrałabym T2 i Adam pewnie też założy, że Bolek jej nie wybierze.

Dlatego Adam zamiast A2 może zastosować A1 (tak samo dobre dla T1 i T4, lepsze przeciw T3) a zamiast A4 - A5 (jw)

Zostaje nam tabelka:
...T1T3T4
A1..r..r..b
A3..r..b..r
A5..b..r..r

Gra strategiami (A1, A3, A5) kontra (T1, T3, T4) jest równoważna grze w papier, kamień, nożyczki z "forami" dla Bolka . Fory oznaczają "jeśli Bolek wygra w pkn, to go uwalniamy, w przeciwnym przypadku losujemy kostką uwolnionego.

No a w grze w papier kamień nożyczki każde posunięcie jest tak samo dobre:)

[taria]

> Fory oznaczają "jeśli Bolek wygra w pkn, to go uwalniamy, w
> przeciwnym przypadku losujemy kostką uwolnionego.

Oczywiście nie kostką tylko monetą, czyli z rozkładem 50/50...