Matematyka gier - kombinacje i probabilistyka

[BartP]

Ja to chyba kiedyś liczyłem i wyszło mi 1/2.

[MichalStajszczak]

Ja to chyba kiedyś liczyłem i wyszło mi 1/2.

Za szybko zepsułeś zabawę, bo to jest niestety prawidłowa odpowiedź.

W takim razie pytanie nieco trudniejsze w tym samym settingu:
Każdy z tych stu żetonów układamy na losowych polach (oczywiście każdy na innym). Jakie jest prawdopodobieństwo, że żaden z nich nie trafi na właściwe pole?
A jakie byłoby prawdopodobieństwo, że żaden nie trafi na właściwe pole, gdyby tych pól i żetonów było nie 100 lecz 1000?

[PytonZCatanu]

1. Ja swoją odpowiedź zamieściłem w spoilerze i uprasza się na przyszłość też tak robić

2. Napiszecie krótkie wyjaśnienie jak wyszła ta 1/2? Trudno mi sobie to wyobrazić

[ArnhemHorror]

Każdy z tych stu żetonów układamy na losowych polach (oczywiście każdy na innym). Jakie jest prawdopodobieństwo, że żaden z nich nie trafi na właściwe pole?
A jakie byłoby prawdopodobieństwo, że żaden nie trafi na właściwe pole, gdyby tych pól i żetonów było nie 100 lecz 1000?

Spoiler:

Policzyłem na szybko w głowie i w pierwszym przypadku wyszło mi 1/100… W drugim się poplątałem

Edit: w drugim 9/10 - nie doczytałem, że również żetonów ma być 1000, i wtedy wychodzi mi 1/1000 tą samą metodą, ale to chyba wciąż nie jest dobry wynik

[MichalStajszczak]

Policzyłem na szybko w głowie

Obawiam się, że musisz policzyć wolniej i może "poza głową"

[MichalStajszczak]

Ja swoją odpowiedź zamieściłem w spoilerze i uprasza się na przyszłość też tak robić

Słuszny wniosek - dlatego też napisałem, że BartP "za szybko popsuł zabawę"

[Arius]

Spoiler:

50%

Na szybko liczyłem, więc mogłem coś przeoczyć.

Poprawiłem.

[eson83]

W takim razie pytanie nieco trudniejsze w tym samym settingu:
Każdy z tych stu żetonów układamy na losowych polach (oczywiście każdy na innym). Jakie jest prawdopodobieństwo, że żaden z nich nie trafi na właściwe pole?

Spoiler:

0 (twierdzenie o punkcie stałym) - nie analizowałem całej dyskusji, wiec standardowo "nie wiem ale sie wypowiem"

A jakie byłoby prawdopodobieństwo, że żaden nie trafi na właściwe pole, gdyby tych pól i żetonów było nie 100 lecz 1000?

Spoiler:

0 (j.w.)

[Arius]

W takim razie pytanie nieco trudniejsze w tym samym settingu:
Każdy z tych stu żetonów układamy na losowych polach (oczywiście każdy na innym). Jakie jest prawdopodobieństwo, że żaden z nich nie trafi na właściwe pole?

Spoiler:

0 (twierdzenie o punkcie stałym) - nie analizowałem całej dyskusji, wiec standardowo "nie wiem ale sie wypowiem"

A jakie byłoby prawdopodobieństwo, że żaden nie trafi na właściwe pole, gdyby tych pól i żetonów było nie 100 lecz 1000?

Spoiler:

0 (j.w.)

Eee czyli załóżmy że mamy przestrzeń wszystkich losowych rozłożeń. Prawdopodobieństwo zero oznaczałoby, że wśród nich nie ma ani jednego który by spełniał powyższe założenie. A to chyba nie jest prawda.
Więc obstawiałbym, że jest to liczba większa od 0.

[MichalStajszczak]

Więc obstawiałbym, że jest to liczba większa od 0.

To prawda. Ale nie jest to ani 50% ani 90%.

[Arius]

Więc obstawiałbym, że jest to liczba większa od 0.

To prawda. Ale nie jest to ani 50% ani 90%.

Nie neguję tego. Aktualnie jestem na pewnym wydarzeniu i z doskoku patrzyłem. Jak będę miał chwilę to zastanowię się jak to policzyć. Teraz jedynie znalazłem moment by ogarnąć Twoją zagadkę i wyjaśnić, że to na pewno nie jest 0.

[PytonZCatanu]

Ale jak tam wychodzi 1/2?

[Arius]

Ale jak tam wychodzi 1/2?

Są różne metody. Ja użyłem tej zwanej drzewkiem.

[Abizaas]

Każdy z tych stu żetonów układamy na losowych polach (oczywiście każdy na innym). Jakie jest prawdopodobieństwo, że żaden z nich nie trafi na właściwe pole?

Spoiler:

!100/100! = 0.3679

A jakie byłoby prawdopodobieństwo, że żaden nie trafi na właściwe pole, gdyby tych pól i żetonów było nie 100 lecz 1000?

Spoiler:

j.w., 0.3679 x 10^-2336

Wyjaśnienie tutaj:
https://en.wikipedia.org/wiki/Derangement

[MichalStajszczak]

Wyjaśnienie tutaj:

Jest polska wersja artykułu o Nieporządku i podsilni.
Dla dwóch żetonów to prawdopodobieństwo jest 50%, dla trzech 33,3%, dla czterech 37,5%, dla pięciu 36,7% a później dość szybko zbiega do 1/e = 36,8% więc dla 100 i 1000 różnica jest niewielka.

[MichalStajszczak]

Ale jak tam wychodzi 1/2?

Generalnie dla każdej liczby żetonów n>1 mamy 50%. Można to udowodnić "rekurencyjnie", analizując kolejne liczby od 2 wzwyż.
Dla n=2 wynik jest oczywisty.
Dla n=3 mamy 3 możliwości ulokowania żetonu numer 1. Jeżeli trafi na pozycję 1, to drugi i trzeci zajmą swoje miejsca. Czyli dla ostatniego mamy 100% szans na właściwe położenie. Jeżeli żeton 1 trafi na pozycję 3, to żeton 3 ma zero szans, żeby tam się znaleźć. (Tak jest zresztą dla każdego n - gdy pierwszy żeton trafia na pozycję 1, n-ty żeton ma 100% szans na właściwą pozycję, a gdy pierwszy zajmie miejsce n-tego, to 0%.) A co będzie, gdy żeton 1 trafi na pozycję 2? Wtedy żeton 2 ma do wyboru dwa miejsca: 1 i 3, z prawdopodobieństwem 50% dla każdego z nich. Mamy zatem 1/3 * 100% + 1/3 * 50% + 1/3 * 0% co daje 50%.
Dla n=4 przypadki trafienia żetonu 1 na miejsce 1 i ostatnie dają efekt analogiczny jak dla n=3 z tą tylko różnicą, że teraz każdy z tych przypadków ma po 1/4 szans na zaistnienie. Jeżeli żeton 1 trafi na pozycję 3, to żeton 2 zajmie swoje miejsce i mamy opisana wyżej sytuację z trzema żetonami. Jeżeli żeton 1 trafi na pozycję 2, to od tej chwili żeton 2 przejmuje rolę żetonu 1 i znowu możemy sprowadzić to do układu trzech żetonów. A zatem w obu tych "pośrednich" sytuacjach mamy po 50% szans na to, by ostatni żeton zajął właściwe miejsce.
To samo rozumowanie możemy przeprowadzić dla każdej kolejnej wartości n.
Można też przeprowadzić rekurencję od końca. Załóżmy, że żeton 1 trafił na pozycję n-1 czyli w podstawowej wersji 99. Wtedy wszystkie żetony od 2 do 98 trafiają na swoje miejsca. A żeton 99 może z prawdopodobieństwem 50% trafić na miejsce 1 (i wtedy żeton 100 zajmuje swoja pozycję) albo z prawdopodobieństwem 50% na miejsce 100 i wtedy ostatni żeton nie może tam się znaleźć. A teraz załóżmy, że żeton 1 trafia na miejsce n-2 czyli 98. Żetony 2-97 zajmują oczywiście swoje pozycje, a żeton 98 może zając miejsca 1, 99 i 100. Dwa skrajne przypadki dają oczywisty rezultat, a zajęcie przez żeton 98 miejsca 99 sprowadza problem do sytuacji, gdy miejsce 99 zajął żeton 1.

Możesz znaleźć inne rozwiązania zadania (w oryginalnej formie z pasażerami samolotu, a nie żetonami) wpisując w wyszukiwarkę:

One hundred people line up to board an airplane. Each has a boarding pass with assigned seat. However, the first person to board has lost his boarding pass and takes a random seat.

[Arius]

Ale jak tam wychodzi 1/2?

Generalnie dla każdej liczby żetonów n>1 mamy 50%. Można to udowodnić "rekurencyjnie", analizując kolejne liczby od 2 wzwyż.

Zrobiłem tak samo. Obliczyłem Dla 2, 3 i 4. I uznałem, że nie ma żadnych powodów by dla większych n miało być inaczej.

[BartP]

Ja to zrobiłem tak samo, a udowodniłem przez indukcję .

[PytonZCatanu]

Mega ciekawy filmik

Planszówki, chwazi i matematyka

[MichalStajszczak]

Mega ciekawy filmik

Artykuł na temat "Go first dice"

[MichalStajszczak]

W dzisiejszej maturze z matematyki jest zadanie powiązane z grami

Tomek i Romek postanowili rozegrać między sobą pięć partii szachów. Prawdopodobieństwo wygrania pojedynczej partii przez Tomka jest równe 1/4 . Oblicz prawdopodobieństwo wygrania przez Tomka co najmniej czterech z pięciu partii. Wynik podaj w postaci ułamka zwykłego nieskracalnego

[minimati]

Ostatni raz coś wspólnego z probabilistyką miałem na studiach, w związku z czym mogę gadać głupoty, ale:

Spoiler:

Wydaje mi się, że wystarczy użyć tutaj schematu Bernoulliego dwa razy:
mamy n=5 prób, w pierwszym przypadku liczymy prawdopodobieństwo k=4 sukcesów, w drugim k=5 sukcesów, a wyniki sumujemy, co daje 1/64.

[KOSHI]

17/25 ???

[citmod]

17/25 ???

Tak tylko zauważę, że wyszła Ci znacznie wyższa szansa na wygranie większości partii tj. 4 z 5 partii (Tobie wyszło 68%) mimo, że szansa na wygranie pojedynczej partii jest <50% (dokładnie 25%). Zastanów się i spróbuj ponownie

[BartP]

Spoiler:

Ja tam Bernoulliego nie znam, ale po mojemu to:
Pr-o wygranej wszystkich gier + pr-o wygrania 4 z 5.
Pr-o wygranej wszystkich gier = (1/4)^5 = 1/1024
Pr-o wygranej czterech z pięciu = 1/4 * 1/4 * 1/4 * 1/4 * 3/4 * 5 - trzeba domnożyć razy 5, bo którąś tam ma przegrać, pierwszą, drugą... na pięć sposobów to się może stać. = 15/1024
Suma = 1/1024 + 15/1024 = 16/1024 = 1/64