Jak się ustawić, by nie wyciągnąć złamanej zapałki?

Każdy z nas doskonale zna grę polegającą na ciągnięciu zapałek, z których jedna jest złamana. Ten sposób losowania stosuje się często, gdy trzeba wybrać spośród kilku osób jedną. Ten, kto wyciągnie złamaną zapałkę, przegrywa. To metoda stara chyba jak same zapałki, a pewnie i starsza, bo równie dobrze można ciągnąć źdźbła słomy, patyki i wszystko, czym tylko daje się przeprowadzić takie losowanie.

Równie stary jak sama gra jest spór dotyczący strategii przyjmowanej przez uczestników podczas ciągnięcia zapałek. Są tacy, którzy uważają, że najkorzystniej być na początku kolejki losujących, bo wtedy jest najwięcej całych zapałek, a w związku z tym, prawdopodobieństwo przegranej najmniejsze. Inni – przeciwnie – wolą losować na końcu, dedukując, że wówczas jest największa szansa, że złamaną zapałkę wyciągnie ktoś przed nimi.

Zastanówmy się, jaka strategia w tej sytuacji jest odpowiednia. Innymi słowy – w którym miejscu kolejki losujących najlepiej się ustawić, aby zminimalizować ryzyko przegranej?

Aby odpowiedzieć na to pytanie wyobraźmy sobie przebieg losowania, w którym biorą udział Ania, Basia, Czesio i Dusia. Ania uważa, że najlepiej być na początku i jako pierwsza będzie ciągnąć zapałkę. Na końcu natomiast ustawiła się Dusia, która twierdzi, że zwiększy swoje szanse, gdy będzie losować jako ostatnia.

Mamy zatem czwórkę graczy i cztery zapałki, z których jedna jest złamana. Przebieg całego losowania możemy przedstawić na grafie nazywanym przez matematyków drzewem stochastycznym.

Pierwsze rozgałęzienie reprezentuje losowanie zapałki przez Anię. Prawdopodobieństwo wylosowania złamanej zapałki wynosi ¹/₄. Gdy Ania wyciągnie złamaną zapałkę – przegrywa, a gra kończy się.

Gdy  Ania wyciągnie całą zapałkę, do losowania podchodzi Basia. Obrazuje je drugi poziom naszego drzewa. Prawdopodobieństwo przegranej Basi oblicza się mnożąc ³/₄ (prawdopodobieństwo, że Ania nie zakończy gry) przez ¹/₃ (prawdopodobieństwo wyciągnięcia złamanej zapałki przez Basię – zwróć uwagę, że zostały 3 zapałki, więc szansa wyciągnięcia złamanej wynosi teraz ¹/₃). Po skróceniu ułamków dostajemy … ¹/₄.

Jeżeli Basia nie przegra – losuje Czesio. Szansa, że to on zakończy grę obliczana jest podobnie. Mnożymy ³/₄ (Ania nie przegrywa) przez ²/₃ (Basia nie przegrywa), a następnie przez ¹/₂ (Czesio wyciąga złamaną zapałkę).

Gdy i on będzie miał szczęście i wyciągnie całą zapałkę, pozostaje już tylko jedna – złamana – zapałka, którą musi wyciągnąć Dusia. Prawdopodobieństwo przegranej Dusi obliczamy następująco: ³/₄ razy ²/₃ razy ¹/₂ razy 1 - czyli ¹/₄ !

Jak widać, każdy ma dokładnie taką samą szansę na wyciągnięcie złamanej zapałki, bez względu na to, w którym miejscu kolejki się ustawi. Oczywiście nasz wniosek dotyczy również innej liczby osób biorących udział w losowaniu. Bardzo łatwo pokazać, że zawsze dla n graczy prawdopodobieństwo przegranej wynosi ¹/_n.

Tak więc nie ma dobrej strategii, którą moglibyśmy zastosować podczas losowania zapałek. To czy jesteśmy pierwsi, czy ostatni, nie ma w tej sytuacji żadnego znaczenia.

Czytaj dalej »

Leonhard Euler i królewieckie mosty

Przed świętami mogliśmy przeczytać o najpiękniejszym wzorze matematyki, podanym w XVIII wieku przez Leonharda Eulera. Nie jest to wszak jedyne osiągnięcie tego wybitnego matematyka. Jego wkład w rozwój matematyki jest tak wielki, że współczesny mu Pierre Simon de Laplace miał wyrazić się na jego temat "Czytajcie Eulera, czytajcie go – jest mistrzem nas wszystkich".

Leonhard Euler dzięki stworzonym przez siebie licznym podręcznikom spopularyzował wiele konwencji zapisu matematycznego, miał olbrzymi wkład do analizy matematycznej i analizy zespolonej (włączając najpiękniejszy wzór matematyki), przyczynił się do rozwoju teorii liczb dowodząc wielu jej twierdzeń, odnosił sukcesy na polu matematyki stosowanej, fizyki, astronomii, a także logiki.

Tym co jednak stawia Eulera w szeregu wielkich twórców i odkrywców jest badane przez niego zagadnienie mostów królewieckich, które zapoczątkowało rozwój teorii grafów. Czego dotyczył ten problem i dlaczego stał się tak ważny dla rozwoju matematyki?

W XVIII wieku, w czasach, gdy Euler zajmował się problemem mostów, Kaliningrad, będący wówczas Królewcem, a nazywany również Königsbergiem należał do Królestwa Prus. Wyspy leżące na przepływającej przez miasto Pregole połączone były między sobą i z brzegami rzeki siedmioma mostami w sposób przedstawiony na poniższej grafice.

Problemem, nad którym pracował szwajcarski matematyk było ustalenie trasy wędrówki po Królewcu w taki sposób, by odwiedzić każdy z siedmiu mostów i przejść przez niego tylko raz. Na gruncie teoretycznym rozmieszczenie mostów można przedstawić w postaci grafu, takiego jak na rysunku, gdzie węzły są wyspami i brzegami Pregoły, a linie (krawędzie grafu) drogami prowadzącymi do nich, czyli mostami Królewca.

Euler wykazał, że taki spacer jest niemożliwy, a decyduje o tym nieparzysta ilość krawędzi wychodzących z każdego węzła (z każdego miejsca w Königsbergu wyprowadzają nas 3 lub 5 mostów). Rozważając ogólniejszy problem - jakie warunki musi spełnić graf (topografia miasta) aby taka wędrówka była możliwa - Euler doszedł do wniosku, że liczba węzłów, w których spotyka się nieparzysta liczba krawędzi musi być równa 0 lub 2, w przeciwnym razie, sytuacja będzie podobna do królewieckiej.

Tak powstała, potężnie dziś rozbudowana, teoria grafów. Dodać jeszcze należy, że całe zagadnienie opublikował Euler w 1741 roku w pracy Solutio problematis ad geometriam situs pertinentis w Commentarii academiae scientiarum Petropolitanae, która obecnie uznawana jest za pierwszą opisującą ten nowy wówczas dział matematyki.

Czytaj dalej »