[M.....k]

100 kolejno ponumerowanych więźniów zostaje skazanych na śmierć. Aby uniknąć kary, każdy z więźniów, po kolei, podchodzi do szafy mającej 100 skrytek: w każdej z nich jest karteczka z numerem 1-100. Aby przeżyć, każdy więzień, mając 50 prób, musi znaleźć karteczkę ze swoim numerem. Więźniowie nie mogą się ze sobą komunikować po tym, gdy pierwszy z nich zacznie otwierać skrytki. Jaką strategię powinni oni przyjąć, aby zmaksymalizować swoją szansę na przeżycie?

Próbując całkowicie losowo, każdy więzień ma 50% szans na wyciągnięcie kartki, więc szansa na przeżycie wynosi (1/2)^100 ~ 0,0000000000000000000000000000008.

#matematyka #zagadki #zagadkilogiczne

[V.....x]

Jeśli zostają w pokoju to:

[Wykopaliskasz]

@MaIutkiCzlowiek: Coś czuję, że jak poznamy odpowiedź, to zacznie się dyskusja, czy ona rzeczywiście ma sens, bo też rozważałem rozwiązanie podane przez @niepokonany i mnie nie przekonało.

[M.....k]

@buszmen007: @PanQbs: @Wykopaliskasz: @babisuk: @emcter: @niepokonany: @zapoznalem: @Vanatox @Kapitalis

Rozwiązanie:


Prawdopodobieństwo wygranej więźniów wynosi wtedy


Czemu?





Jaka jest na to szansa?


źródło:

[niepokonany]

@MaIutkiCzlowiek: Wydaje mi się, że moje rozwiązanie jest prawidłowe. Liczby w skrzynkach są losowe, więc każdy z więźniów musi otworzyć unikalny zestaw skrzynek żeby zoptymalizować szanse powodzenia i moje rozwiązanie to zapewnia. Rozwiązanie zagadki które wkleiłeś daje po prostu przykład innego systemu, który robi dokładnie to samo, co ja opisałem i w mojej opinii ma taką samą szansę powodzenia. Udowodnij mnie źle.

[M.....k]

@niepokonany: nie czuję się wystarczająco kompetentny, by ci udowodnić źle. Może to pomoże:

http://puzzling.stackexchange.com/a/69

[Wykopaliskasz]

@MaIutkiCzlowiek: Mam zastrzeżenia do stwierdzenia "jeśli najdłuższy cykl jest długości <= 50, każdemu uda się znaleźć swoją kartkę".

Nieprawda. Nadal jest duża szansa na nietrafienie. Powiedzmy, że są cztery cykle, wszystkie o długościach 25. Kartka jest w jednym z nich, a sprawdzić można jedynie 50 kolejnych kartek. Na trafienie mamy szansę równą 1/4+1/3=7/12=58%, a nie 100% jak w powyższym stwierdzeniu.

[bear2112]

@MaIutkiCzlowiek: @niepokonany: nie wiem jak to zapisac ale chodzi o rozbicie permutacji na cykle rozlaczne.

[M.....k]

@Wykopaliskasz: zaczynanie od skrytki ze swoim numerem gwarantuje, że wybieramy właściwy cykl (tj. ten, w którym natrafimy na swój numer). Nie istnieje opcja, że przelecimy cały cykl i nie znajdziemy swojej kartki.

[pirus]

@Wykopaliskasz: jak sa 4 cykle o dlugosci 25 to masz 100% szans na uratowanie sie

[Wykopaliskasz]

@MaIutkiCzlowiek: Dlaczego? Zaraz mogę Ci rozpisać przykład cyklu, w którym nie będzie Twojej kartki. Przecież są losowe.

[Wykopaliskasz]

@pirus: W takim razie nie rozumiem znaczenia słowa "cykl".

[M.....k]

@Wykopaliskasz: rozpisz.

[bear2112]

@Wykopaliskasz: najpierw zobacz co to jest cykl i skladanie permutacji to zrozumiesz.

[pirus]

@Wykopaliskasz: napisz sobie na kartce dowolny cykl np dla wieznia #1, ktory otwiera #1 skrzynke

[Wykopaliskasz]

@MaIutkiCzlowiek, @pirus: No dobra, teraz widzę.

[PanQbs]

Masz 50 cykli (numery wskazuja na siebie parami). i zonk

[pirus]

@PanQbs: jak wskazuja na siebie parami, to wszyscy sa uratowani i dodatkowo w najkrotszym czasie ;]

[Wykopaliskasz]

@PanQbs: Myślisz w ten sam sposób, co ja przed chwilą. W tym rozumowaniu jest błąd. Mi pomogło zaczęcie rozpisywania dowolnego przykładu.

@pirus: Najkrótszy czas byłby, gdyby wszystkie cykle były długości 1, czyli numer szuflady odpowiadałby numerowi w środku.

[pwone]

@MaIutkiCzlowiek: Przekonałeś mnie. A i nawet tłumaczenie nie jest takie złe jeśli ktoś nie chce na siłę dorabiać jakiś schematów pozakonkursowych. Ogólnie w zadaniu chodzi o to, aby więźniowie nie otwierali w większości tych samych skrytek.