Jutro finał
Organizacja turnieju tenisowego, czyli ustalenie zasad dobierania w pary zawodników do pierwszej i kolejnych rund rozgrywek, to wprawdzie nie wyższa matematyka, ale też nie taka prosta sprawa. W turniejach wielkoszlemowych przyjęty jest system pucharowy z rozstawianiem 32 najlepszych w rankingu (dawniej bywało 16). Generalnie chodzi o to, aby dwaj gracze stawali w szranki tym później, im wyższy i bliższy sobie poziom reprezentują. W praktyce układ rozgrywek w dobiegającym finału turnieju Australian Open 2008 można uznać za efekt zmagań z poniższą łamigłówką.
Należy dobrać w pary do pierwszej rundy 128 zawodników, wśród których znajduje się 32 uprzywilejowanych (oznaczonych kolejnymi liczbami od 1 do 32, odpowiadającymi ich miejscu w rankingu), oraz ustalić zasadę „parowania” w kolejnych rundach, w taki sposób, aby przy założeniu, że lepszy w rankingu będzie zawsze zwyciężał, grali:
– w trzeciej rundzie 32 uprzywilejowani,
– w czwartej rundzie oznaczeni liczbami od 1 do 16,
– w ćwierćfinale ósemka najlepszych (1 – 8),
– w półfinale czołowa czwórka (1 – 4),
– w finale pierwsza dwójka rankingu, czyli Federer i Nadal.
Choć to nie wielka filozofia, jednak obawiam się, że większość z Państwa miałaby mały zgryz z tym zadaniem, czyli z zaprojektowaniem poniższej tabelki, zastosowanej w turnieju Australian Open.
W górnym rzędzie znajdują się pary skompletowane do pierwszej rundy; iksy oznaczają graczy nierozstawionych. W kolejnych rundach spotykają się zwycięzcy z sąsiednich par, zaczynając oczywiście dobieranie zawsze od lewego lub prawego brzegu.
Jak widać z rozpisania kolejnych rund, podane w zadaniu warunki są spełnione, czyli drabinka (klasyczna turniejowa wersja tabelki, która powstanie po jej obróceniu w lewo o 90 stopni) działa.
Byłoby rzecz jasna cokolwiek nudnawo, gdyby wszystko przebiegało „sprawiedliwie”, czyli zgodnie z rankingiem. Na szczęście nigdy nie brakuje jeśli nie sensacji, to przynajmniej niespodzianek: rozstawieni przegrywają w pierwszej rundzie (w tym roku pięciu), a zdarza się, że nierozstawieni przebijają się nawet do finału (ostatnio Kuerten w 1997 roku we French Open, a teraz Tsonga).
Fanom tenisa, którzy podobnie jak ja będą śledzić przebieg finału Djokovic – Tsonga, życzę wielu emocji (postawiłem na Francuza), a wszystkim proponuję zadanie domowe – jeszcze jedną powtórkę z propedeutyki teorii prawdopodobieństwa.
Raz w roku w Szanghaju organizowany jest puchar mistrzów (Tennis Masters Cup), w którym startuje tylko pierwsza ósemka rankingu. Załóżmy, że w tym turnieju byłby stosowany system pucharowy, a o zestawieniu par w pierwszej rundzie rozstrzygałby los, czyli gracze wyciągali by numery określające ich miejsca w drabince (w rzeczywistości prowadzone są rozgrywki grupowe, podobnie jak w Mundialu). Załóżmy też, że wyżej notowany zawsze będzie wygrywał. Oczywistym jest, że wówczas w turnieju zwycięży pierwszy w rankingu. A jakie jest prawdopodobieństwo, że w takiej sytuacji drugi w rankingu dotrze do finału?
Przypominam, że odpowiedzi, aby nie stały się podpowiedziami, uwalniam po dniach paru.
Komentarze
„Pucharowy Szanghaj”
Jeśli wyżej notowany gracz zawsze będzie wygrywał oznacza to, że drugi w rankingu dotrze do finału wtedy i tylko wtedy, gdy nie spotka się wcześniej z pierwszym. Aby to mogło nastąpić musi znaleźć się w drugiej połówce drabinki, czyli na jednej z czterech pozycji startowych. Wszystkich możliwości jest 7 (bo jedna zajęta już przez lidera), a więc szukane prawdopodobieństwo wynosi 4/7.
Ponieważ pytanie było proste, można pokusić się o podanie zależności ogólnej dla n graczy (co zresztą też nie jest trudne). Jeśli n będzie parzyste (jak zazwyczaj) wówczas prawdopodobieństwo dotarcia drugiego gracza do finału wyniesie (rozumując analogicznie jak poprzednio) n/2(n-1). Jeśli n będzie nieparzyste (i w pierwszej rundzie ktoś otrzymuje wolny los) to, ponieważ „połówki” wtedy nie są równe 😉 (jedna ma (n-1)/2 zawodników, druga – (n+1)/2 ), wynik można obliczyć stosując prawdopodobieństwo całkowite (pierwszy gracz w „połówce” – nazwijmy – A, drugi w „połówce” B lub pierwszy w B, drugi w A):
(n-1)/2/n*(n+1)/2/(n-1) +
+ (n+1)/2/n*(n-1)/2/(n-1) =
= (n+1)/2n
A swoją drogą, to dziwne, że turniej w rzeczywistości rozgrywany jest grupami. W końcu ma w nazwie puchar… 😉
Pozdrawiam
AB
Największą zagadką tym razem jest chyba zamieszczony rysunek przykładowej tabeli. 😉
W związku z tym parę słów o metodzie rozstawiania:
Przyjmijmy dla uproszczenia założenie, że wszystkich graczy jest 2^n.
Dzielimy drabinkę na dwie połówki. W jednej (w sumie nie ma znaczenia, na której dokładnie pozycji) umieszczamy najlepszego zawodnika, w drugiej – drugiego w kolejności. Następnie każdą z połówek znów dzielimy na pół i w tych dwóch ćwiartkach, w których nie ma jeszcze nikogo, sytuujemy trzeciego i czwartego w rankingu. Potem z kolei na pół dzielimy każdą ćwiartkę i w czterech pustych „jednych ósmych” znajdują swe miejsca gracze: piąty, szósty, siódmy i ósmy. W ten sposób możemy postępować dowolnie długo, aż ulokujemy wszystkich rozstawionych zawodników. Pozostali zajmują wolne jeszcze pozycje. Oczywiście rozstawionych graczy nie może być więcej niż połowa. Taki sposób gwarantuje spełnienie założeń, tzn., że odpowiednio silni zawodnicy nie spotkają się ze sobą zbyt wcześnie.
Pozdrawiam
AB
w pierwszej chwili przyszła do głowy myśl o 50%, ale po gruntownym kilkusekundowym przemyśleniu stawiam na 4/7 czyli 57,1%
Albo nie zrozumialem, albo to zadanie jest stanowczo za proste:
– gracz nr 2 dojdzie do finalu, jesli nie znajdzie sie w tej samej polowce drabinki, co gracz z nr 1
– miejsc w drabince (poza nr 1) jest 7
– miejsc w „drugiej” polowce drabinki – 4
Zatem prawdopodobienstwo wynosi 4/7.
Dla podanych warunków prawdopodobieństwo , że „drugi” dotrze do finału wynosi 4/7 .
Do wyniku można dojść rysując turniejową drabinkę .
Do finału awansują po jednym najwyższym numerze rankingowym z pierwszej i drugiej oraz z trzeciej i czwartej pary ćwierćfinałowej .
„Dwójka” jest w którejś parze ćwierćfinałowej . Jeżeli „jedynka” jest jedną z trzech pozostałych to spotkają się wcześniej niż w finale . Jeżeli „jedynka” jest jedną z czterech osób w drugiej parze par to spotkają się w finale . A zatem na siedem możliwości cztery dają „dwójce” finał .
Inne rozumowanie prowadzące do tego samego wyniku:
„Dwójka” zagra w finale jeżeli nie spotka „jedynki” ani w ćwierćfinale , ani w półfinale (zdarzenia zależne – prawdopodobieństwo równe iloczynowi prawdopodobieństw tych zdarzeń).
W ćwierćfinale „dwójka” może spotkać jedną z siedmiu osób , z których sześć jest do ogrania. Prawdopodobieństwo , że nie spotka „jedynki” wynosi 6/7.
W półfinale może spotkać jedną z trzech osób , z których dwie nie są „jedynką” . Prawdopodobieństwo wynosi 2/3 .
Ostatecznie prawdopodobieństwo na finał wynosi 6/7×2/3=4/7.
A jakie jest prawdopodobieństwo ,że w finale zagra rankingowa „trójka” , „czwórka” itd ?
Ten problem jest nieco trudniejszy.
Moim zdaniem : „3”- 2/7 , „4”- 4/35 , „5”- 1/35 , „6” – 0 , „7” – 0 , „8” – 0 .
Pozdrowienia
AC
A propos mojego wcześniejszego komentarza. Zagadka tajemniczego rysunku tabeli chyba mi się wyjaśniła.
No cóż… było na niego kliknąć i wszystko stałoby się wyraźne.
Ale ze mnie gapa… 🙂
Pozdrawiam
AB
Jeszcze parę słów w związku z poprzednim wpisem (między innymi dlaczego wyszło mi tylko siedem rozwiązań).
Otóż przyjąłem pewne dodatkowe założenie (widać niesłusznie, skoro nikt inny tego nie zrobił), że po obu stronach równości, na każdym etapie obliczeń musimy mieć wartość całkowitą. Dlatego też w moim przypadku wyrażenie typu 7:28×60 było niewłaściwe (po drodze mamy 0.25), choć np. 60×7:28 już w porządku. Podobnie wykluczyłem 87:2×0 (najpierw mamy ułamek, który dopiero potem zostaje wyzerowany), zostawiając za to 0x87:2 itd.
Dodam jeszcze, że wbrew pozorom to wcale nie było ułatwienie, a wręcz przeciwnie: oprócz sprawdzenia równości należało jeszcze kontrolować rezultaty pośrednie.
Czym się kierowałem?
W przypadku „uszlachetnionego” Hexa-Trexu nie ma to w sumie znaczenia, ale w przypadku ogólnym chciałem wyeliminować rozwiązania tego typu, jakie są rezultatem np. tych dwóch ułożonych przeze mnie (postanowiłem trochę zrobić konkurencję Robertowi 😉 ) łamigłówek:
__=_4
_8_5_1
6_: _9_:
_+_7_2
__3_0
__7_:
_2_4_8
=_3_+_9
_6_5_1
__0_:
Obie należą do odmiany „półszlachetnej” 😉 , tzn. zawierają (po jednej) wszystkie dziesięć cyfr, natomiast zamiast czterech działań mają tylko dodawanie i dwa dzielenia. Ta modyfikacja została wprowadzona bynajmniej nie dla uproszczenia, ale jak najbardziej celowo i z premedytacją. Diagramy swym kształtem przypominają w pełni „szlachetną” wersję – zostały tylko (w związku z jednym polem mniej) pozbawione górnego „czubka”.
Zgodnie z założeniami zadania te mają dokładnie dwa rozwiązania, oba całkowicie różne – nie pokrywa się ani jedna liczba!
I to w dodatku jakie rozwiązania! 😉
Starałem się, aby w każdej łamigłówce przynajmniej jedno z nich było szczególnie „ciekawe” 😉 .
Cóż… ujawnię je od razu. Nie chcę się nad nikim znęcać – później mógłby mnie nie lubić, albo, co gorsza, miałbym go na sumieniu. „Komputerowcy” oczywiście poradzą sobie z nimi bez problemu (w końcu maszyna jest cierpliwa), ale liczący samodzielnie, o ile stosunkowo szybko nie zrezygnują, mogą w stanie ciężkim wylądować… lepiej już nie mówić gdzie. 😉
Oba zadania są bowiem z gatunku „sado-maso”, tzn. „maso” – gdybyśmy chcieli je rozwiązywać samodzielnie, a „sado” – gdybyśmy je „usłużnie” podrzucili komuś, kogo nie lubimy. 🙂
A więc podaję rozwiązania.
Pierwsze:
791:203+6:58 = 4
592:14 = 86:7+30
Drugie:
1+98:742 = 60:53
3+4:72 = 605:198
Pozdrawiam
AB
PS: Te zadania proszę oczywiście traktować jako żart 🙂 (jeżeli ktoś do tej pory jeszcze na to nie wpadł).
Mysle Panie Marku, ze nie docenia Pan swoich czytelnikow – w kwestii ulozenia tabelki. Nawet wiecej – mysle, ze spora czesc rozwiazalaby taki problem:
Ile jest roznych sposobów ulozenia takiej tabelki dla 128 graczy?
(Sposoby nazywamy roznymi, jesli na conajmniej jednym etapie turnieju mozliwe sa mecze miedzy innymi przeciwnikami).
Np. Ustawienia (parujemy „po kolei”)
1 2 3 4
i
4 3 2 1
są „podobne” (tj. nie sa różne)
Ale
1 3 2 4 jest różny od poprzednich.
Prawdopodobieństwo dotarcia drugiego w rankingu gracza do finału jest takie samo jak szansa, że w finale nie zagra.
Pozdrawiam