Zagadkę o czekoladkach można rozwiązać na kilka sposobów. Pokażę ten najciekawszy (moim zdaniem). Mianowicie... rozwiążemy ją za pomocą rekurencji.
Załóżmy na chwilę, że w pudełku są dwie czekoladki: jedna biała i jedna czarna. W takim przypadku oczywistym jest, że szanse na to, że biała będzie ostatnia, wynoszą dokładnie 50%.
A teraz załóżmy na chwilę, że udało nam się udowodnić, że prawdopodobieństwo zakończenia na białej czekoladce wynosi 50% dla pewnej bliżej nieokreślonej liczby czekoladek mniejszej od N. Zobaczmy co stanie się, jeżeli mamy dokładnie N czekoladek: b białych i c czarnych.
Są trzy możliwości: albo (1) wyjmiemy najpierw po kolei b białych czekoladek (i wtedy zostaną same czarne), albo (2) wyjmiemy najpierw c czarnych (i wtedy zostaną same białe), albo (3) wyjmiemy trochę czekoladek jednego koloru aż natrafimy na czekoladkę innego koloru.
Zgadza się?
No to teraz spróbujmy wykombinować jaka jest szansa, że wyciągniemy po kolei c czarnych czekoladek: wszystkich możliwych kombinacji kolejności, w której możemy wyjąć czekoladki, jest - zgodnie z rachunkiem prawdopodobieństwa - \(\frac{c!(N-c)!}{N!}\). Ponieważ N-c=b (wiemy, że w pudełku są wyłącznie białe i czarne), ilość tych kombinacji upraszczamy do \(\frac{c!b!}{N!}\).
W drugą stronę podobnie: szansa, że wyciagniemy po kolei b białych czekoladek wynosi \(\frac{b!(N-b)!}{N!}\) czyli po uproszczeniu \(\frac{b!c!}{N!}\).
Widzimy więc, że wyciągnięcie wszystkich czekoladek jednego koloru bez natrafienia na czekoladkę drugiego koloru jest tak samo prawdopodobne, niezależnie od ich ilości oraz wyboru koloru! Czyli możliwość numer (1) oraz numer (2) są tak samo prawdopodobne, a możliwość numer (3) sprawia, że w pudełku zostanie mniej niż N czekoladek, a wiemy przecież, że dla liczby czekoladek mniejszej niż N szanse zakończenia na białej wynoszą 50%.
Dla N=2 wiemy, że p=50%. Z powyższej dedukcji wynika więc, że dla N=3 też wynosi 50%. A więc dla N=4 również. I tak dalej, aż do nieskończoności.
Albo aż nam brzuch pęknie z obżarstwa.
A jak Wam poszło z tą zagadką?
1Pierwszy zameldował się Cichy, który podał poprawną odpowiedź, aczkolwiek używając nieco rozmytego rozumowania:
Algorytm jest całkowicie symetryczny wobec kolorów, więc dowolne rozumowanie dla białej czekoladki będzie identyczne z rozumowaniem dla czarnej i da identyczny wynik, czyli musi to być 50%. Prawdopodobieństwo nie zależy też od początkowej proporcji obu kolorów, bo jeśli któregoś jest znacząco więcej, to będziemy częściej losować dwie lub więcej czekoladek tego koloru z rzędu i proporcja z czasem się wyrówna.
Osobiście powyższa odpowiedź mi się nie podoba (jest mało "matematyczna"), ale... trudno jej zarzucić brak elegancji. W dodatku Cichy jako jedyny zwrócił uwagę na "samoregulację" tego układu - czym większa różnica ilości kolorów, tym bardziej kolory będą się "starały" wyrównać. Zaliczam.
2Drugi był Rozie, który kombinował identycznie jak Cichy:
Nie wiemy ani ile jest czekoladek w pudełku, ani jaki jest ich rozkład. Wiemy tylko, że są białe albo czarne. Każdy układ kolorów i losowań będzie miał równie prawdopodobny układ odwrotny, stąd 50%.
Po przeczytaniu obydwu tych odpowiedzi zdałem sobie sprawę z zasadniczego błędu, jaki popełniłem formułując zagadkę: powinienem był napisać, że w pudełku jest na początku x czekoladek białych oraz y czarnych, dzięki czemu dałbym zgadującym szansę na odrobinę algebraicznego wrestlingu, albo chociaż próbę zrobienia symulacji.
No trudno. Słowo się rzekło, kobyłka cośtam cośtam.
3Chwilę potem rozwiązanie nadesłał Waldek. Co ja mówię, rozwiązanie. Sześć! Oto one:
Rozwiązanie 1. 50% - Nie doszedłem w żaden sposób do wyniku - sytuacja jest czarno-biało doskonale symetryczna, więc po połowie na kolor i tyle.
Rozwiązanie 2. 0% - "ilość białych i czarnych czekoladek" oznacza, że jest ich po nieskończenie wiele. Nigdy nie zjemy wszystkich. Udławimy się, a potem dostaniemy biegunki lub obstrukcji.
Rozwiązanie 3. Błąd w treści zadania - Według dyrektywy 2000/36/WE czekoladę definiuje się jako wyrób otrzymywany z wyrobów kakaowych i cukrów, który zawiera nie mniej niż 35% suchej masy kakaowej ogółem, w tym nie mniej niż 14% suchej odtłuszczonej masy kakaowej. Mówiąc inaczej tzw. "biała czekolada" nie istnieje - to tylko nazwa marketingowa tłustego świństwa dla ubogich.
Rozwiązanie 4. Zagadka ma haczyk, którego, ku… rza stopa, nie dostrzegam. W takim przypadku narzucają się rozwiązania skrajne, czyli 0% albo 100%. Ciemność, widzę ciemność!
Rozwiązanie 5. Nie mam pojęcia.
Rozwiązania 6+. Mam jeszcze kilkanaście pomysłów, ale podejrzewam, że żaden z nich nie zagra w duecie z Twoim.
Jak widać Waldek rozumował identycznie jak pozostali zgadujący i ustalił p=50% bez wdawania się w wyliczanki (uznaję Waldka rozwiązanie numer 1 zgodnie ze starożytną zasadą "pierwsze słowo do dziennika, drugie słowo do śmietnika").
4Nazajutrz rano rozwiązanie nadesłał Butter: 50%, bez uzasadnienia. Zaliczam, po znajomości.
5Sześć minut później przyszła odpowiedź Tywana: "Żaden kolor nie jest w jakikolwiek sposób wyróżniony". No, w końcu mogę się do czegoś przyczepić! Wyróżniłem przecież wyraźnie kolor różowy, poprzez niewymienianie go w warunkach zadania 😉 Mógłbym więc odpowiedzi Tywana nie zaliczyć, gdybym był złośliwy, ale ponieważ nie jestem[citation needed], zaliczam.
Nauczka dla mnie: następnym razem spróbować się wczuć w zgadującego i upewnić się, że zagadka jest sformułowana jak należy!
Dopisanie x i y niczego nie zmienia. Gdybyś napisał, że białych jest 1758, a czarnych 7, to by mogło wprowadzić nieco zamieszania.
Mógłbym poprosić o policzenie p w funkcji x i y…
To ja się przyznaję, że trochę inaczej zrozumiałem treść zadania i moja odpowiedź była dla N prób, nie dowolnego przypadku. Zmyliło mnie jawne dopuszczenie algorytmów, co przy pozostałych danych losowych musiało się skończyć 50/50 w długim okresie. I to miałem na myśli pisząc 50%, zupełnie pominąłem że dla 99 białych i 1 czarnej prawdopodobieństwo jest takie samo co dla 99 czarnych i 1 białej.
Zrozumiałeś tak jak wszyscy pozostali, co mnie tylko utwierdza, że błędnie sformułowałem zadanie 🙂