Losowanie prezentów

WPROWADZENIE

Grupa 20 uczniów pewnej postanowiła zrobić sobie prezent na Mikołajki. Każda osoba napisała na kartce swoje imię (unikalne), wszystkie kartki zostały umieszczone w pudełku, po czym każdy kolejno losował jedną kartkę. 

Jakie jest prawdopodobieństwo, że podczas losowania prezentów przynajmniej jedna osoba wylosuje siebie?

Problem ten rozwiązuje się z wykorzystaniem podsilni – liczbie takich permutacji aby żaden element nie stał na swoim pierwotnym miejscu.

Silnię oznaczamy wykrzyknikiem, np $5!= 5\cdot 4\cdot 3\cdot 2\cdot 1$. Podsilnię też oznaczamy wykrzyknikiem, ale stawiamy go przed liczbą, np $!5$.

Zatem:

Dla 20 osób prawdopodobieństwo, że nikt nie wylosuje siebie to:

$P(A) = \frac{!20}{20!} \approx 36\%$

Czyli prawdopodobieństwo, że przynajmniej jedna osoba wylosuje siebie to:

$P(A’) = 1-\frac{!20}{20!} \approx 64\%$

Zobacz przykład podsilni w arkuszu kalkulacyjnym: Podsilnia

WIęcej o omawianym problemie przeczytasz:

• https://pl.wikipedia.org/wiki/Nieporz%C4%85dek
• https://pl.wikipedia.org/wiki/Podsilnia

KOD W JĘZYKU PYTHON

import random

n = 16
num_trials = 100
count = 0
for i in range(num_trials):
    students = list(range(1, n + 1))
    random.shuffle(students)
    for j in range(n):
        if students[j] == j + 1:
            print(f'Próba {i+1}, osoba {j+1} wylosowała samego siebie')
            count += 1
            break
print(f'\nW {count} z {num_trials} prób, że ktoś wylosował samego siebie.')

⬆️⬆️⬆️ Zobacz w Google Colaboratory

JAK DZIAŁA PROGRAM?

1. Zaczynamy od importu biblioteki random
2. Ustalamy stałą liczbę uczniów w klasie na 20
3. Ustalamy liczbę prób symulacji na 100
4. W pętli for (dla każdej próby) program tworzy listę uczniów za pomocą funkcji range i list() oraz tasuje ją za pomocą funkcji shuffle().
5. W drugiej pętli for (dla każdego ucznia) program sprawdza, czy numer wylosowany dla danego ucznia odpowiada jego własnemu numerowi, a następnie wypisuje informację, że taka sytuacja wystąpiła.
6. W przypadku znalezienia trafienia, program zwiększa wartość zmiennej count (liczba trafień) i przerywa pętlę, aby nie sprawdzać dalszych uczniów. Nie interesuje nas już, czy inny uczeń też siebie wylosuje oraz przyspiesza działanie całego programu.
7. Na końcu program wypisuje informację o liczbie trafień w stosunku do liczby prób.