Rozwiązanie zagadki dla najmądrzejszych

https://xpil.eu/s7j

W postawionej niedawno zagadce pytamy jakie jest prawdopodobieństwo bycia mądrzejszym od każdej z dziewięciu osób wylosowanych z całej populacji wiedząc, że na pewno jesteśmy w górnych 10% tej populacji (ale nie wiadomo w której konkretnie części tych 10%).

Zaczniemy od rozwiązania uproszczonego: skoro nie wiemy w którym kawałku górnego decyla jesteśmy, możemy równie dobrze przyjąć, że jesteśmy w jego połowie (a więc dokładnie na 95%) i sprawdzić ile wynosi prawdopodobieństwo, że nikt z wylosowanych nie trafił powyżej 95%:

0.959≈0.63025 czyli ciut ponad 63%.

Odpowiedź ta jest w przybliżeniu poprawna. Jednak aby rozwiązać zagadkę dokładnie trzeba się jej przyjrzeć nieco bliżej - zobaczymy zaraz, że powyższe przybliżenie daje nam ponad 2% błędu (albo nawet ponad 3%, zależy z której strony patrzeć).

Poprawne rozumowanie przebiega tak:

Spośród 9 wylosowanych osób, część trafi do górnego decyla. Czym więcej ludzi w górnym decylu, tym mniejsze nasze szanse na to, że będziemy wśród nich na samej górze. Po kolei:

  1. Jeżeli do górnego decyla nie trafi ani jeden człowiek, jesteśmy najmądrzejsi. Szansa, że do górnego decyla nie trafi ani jeden człowiek wynoszą 0.99 czyli ~38.74%.
  2. Jeżeli do górnego decyla trafi dokładnie jeden z wylosowanych, nasze szanse są pół na pół. Szansa, że do górnego decyla trafi dokładnie jeden człowiek wynosi 0.1 * 0.98 * 9 czyli ~38.74%. Dzielimy to na dwa (bo pół na pół), czyli około 19.37%. A czemu mnożymy przez dziewięć? Bo tyle jest różnych kombinacji, że jedna osoba jest wśród top 10% a reszta nie.
  3. Jeżeli do górnego decyla trafią dwie osoby, nasze szanse na bycie na topie maleją do 33.(3)%. Szansa na to, że do górnego decyla trafią dwie osoby wynosi 0.12*0.97*36 czyli ~17.21%, a jedna trzecia z tego to okolice 5.74%.
  4. Jeżeli do górnego decyla trafią trzy osoby...
  5. Cztery...
  6. Pięć...

I tak dalej. Uzyskane w każdym kroku procenty sumujemy i na końcu okaże się, że prawdopodobieństwo bycia najmądrzejszym wynosi około 65.13% - i to jest ostatecznie poprawna odpowiedź (zaokrąglona do dwóch miejsc po przecinku). Jest to dwa procent więcej niż rozwiązanie przybliżone zaprezentowane na samym początku. A patrząc od dupy strony, jeżeli w wersji przybliżonej dokonamy niewielkiej zmiany i przesuniemy się o 3.4% "w górę" ze środka naszego decyla, czyli z 50% na 53.4% (a więc z 0.95 na 0.9534), wówczas dziewiąta potęga da nam poprawny wynik - z zadaną dokładnością rzecz jasna.

Oczywiście zamiast ufać matematyce zawsze można przeprowadzić symulację:

from random import random

wygrane = 0
proby = 100000000
for proba in range(proby):
    ja = 0.9 + random() / 10
    inny_madrala = max([random() for x in range(9)])
    if(inny_madrala < ja):
        wygrane += 1
print(wygrane / proby)

Powyższy kawałek kodu przeprowadza 100 milionów prób i liczy ile razy byliśmy najmądrzejsi. U mnie po kilku minutach oczekiwania wyszło 0.65126931 (czyli po zaokrągleniu 65.13%)

A jak Wam poszło?

1Tywan był pierwszy (zgłoszenie nadeszło o 7:39 - dokładnie dwie godziny po publikacji zagadki, to chyba rekord), ale poszedł na łatwiznę i nadesłał odpowiedź przybliżoną 63%, popartą obliczeniem 0.959. Nie zaliczam.

2Kilka godzin później głos dał Jaro, który jednak poszedł całkiem dziwną ścieżką i wyszło mu 0.12%. Rzecz jasna nie zaliczam, ale jestem bardzo zaciekawiony tokiem rozumowania:

3Chwilę później odezwał się Stefek Burczymucha, który jednak zamiast wziąć się za bary z zadaniem, obrócił je w krotochwilę z wynikiem 212.98 🙂 Nie zaliczam.

4Tego samego dnia pod wieczór odezwał się Butter, któremu nie działało wysyłanie odpowiedzi przez standardowy formularz więc przesłał bokiem. Odpowiedź 0.2% (w przybliżeniu (1/2)9) - rozumowanie Buttera pomija całkiem naszą przynależność do górnego decyla. Nie zaliczam.

5Następnego dnia rano swoje rozwiązanie (66.66%) przysłał Rozie, który miał ze wszystkich dotyczasowych zawodników największą szansę trafienia w poprawną odpowiedź, ale zaprzepaścił ją z trzech powodów. Symulacje w Pythonie dawały mu wyniki w okolicach 64.5 - 65.5, więc Rozie... zaokrąglił "na czuja" w górę do 2/3. Drugim błędem było przeprowadzenie symulacji na liczbach całkowitych 0-999 zamiast na ułamkach. Trzecim wreszcie - niewielka liczba prób (tylko 100 tysięcy). Szkoda, bo było blisko 🙂 Nie zaliczam.

6Około południa przyszło zgłoszenie Rafała, który powtórzył rozumowanie Tywana. Nie zaliczam.

7Zaraz potem odezwał się Waldek, któremu formularz też nie chciał działać i nadesłał swoje rozwiązanie pocztą. Poprawne! Gratuluję! Metody Waldka tak do końca nie rozumiem (Waldek jest misiem o zdecydowanie większym rozumku od mojego), prezentuję ją tutaj ku potomności. Szacun.

(C) Waldek, październik 2021

https://xpil.eu/s7j

7 komentarzy

  1. Czy “mądrość” oznacza “inteligencję”? Jeśli nie, to jak się tę mądrość mierzy? Jeśli tak – nie wiem, czy to będzie miało tutaj znaczenie, ale rozkład inteligencji nie jest równomierny, tylko normalny 🙂

    1. Bardzo słuszna uwaga! Faktycznie, w zagadce zabrakło informacji o tym, że rozkład “mądrości” jest równomierny. Do do “mądrość” == “inteligencja” to obydwa pojęcia są na tyle rozmyte znaczeniowo, że szkoda gadać 🙂

  2. Szkoda, że nie wrzuciłeś kodu – nie mam go pod ręką. Wydaje mi się, że użycie liczb całkowitych nie powinno mieć znaczenia. Prędzej właśnie ilość próbek.

    W ogóle podszedłem nieco inaczej i każdorazowo losowałem próbkę 1k osobników, następnie obliczałem dolną granicę górnego decyla z tej próbki. Potem losowałem siebie z zakresu od granicy decyla do maksimum i porównywałem wynik z max z 9 wylosowanych z próbki. Było to o tyle złe podejście, że złożone obliczeniowo, więc rzutujące na ilość prób.

    1. OK, dokopałem się do kodu i się potwierdza. Miałem:
      c = 0
      for k in range(0, 100000):
         a = []
         b = []
         for j in range(0, 1000):
             b.append(random.randint(0, 1000000))
         b.sort()
         for l in range(0, 9):
             a.append(b[random.randint(0, 999)])
         r = b[random.randint(900, 999)]
         if r > max(a):
             c += 1
      print(c)
      Dodatkowa pętla w pętli, służąca do wyznaczania rzeczywistego percentyla jasno widoczna.
      Natomiast samo użycie liczb całkowitych nie jest problemem:
      import random

      wygrane = 0
      proby = 10000000
      for proba in range(proby):
         ja = 900000 + random.randint(0, 100000)
         inny_madrala = max([random.randint(0, 1000000) for x in range(9)])
         if(inny_madrala < ja):
             wygrane += 1
      print(wygrane / proby)
      Wyniki oscylujące wokół prawidłowego w granicach błędu mamy już po 10 mln prób, nawet używając liczb całkowitych. Choć oczywiście ze względu na ostrą nierówność w warunku madrala < ja przedział mądrości wyrażony całkowicie musi być dość duży. Bez tego zaniży wynik.

  3. skoro losowanie odnosi się tylko do czytelników Ignormatyka z których wszyscy są w tym samym decylu –> mamy więc ustalić, jakie jest prawdopodobieństwo, że jestem najmądrzejszy z grupy 10 osób. tak zrozumiałem zapis.

    Ale że to prawdopodobieństwo to nie mam zamiaru się kłócić – niepokoiłby mnie tylko wynik mniejszy od 0 i większy od jedności.

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.