Omówienie zadania Licytacje (III etap XXXIII OI)

Treść zadania

Jest to zadanie komunikacyjne. W zadaniu występuje dwóch uczestników – Algosia i Bajtek. Oboje na początku gry otrzymują ciąg liczb całkowitych długości \(n\) o wartościach wygenerowanych w sposób pseudolosowy z zakresu \([1, m]\) z równym prawdopodobieństwem wystąpienia każdej liczby. Ponadto dana jest liczba całkowita \(k\). Gracze licytują na zmianę coraz większe liczby całkowite (jednocześnie deklarując, czy jest to koniec gry, czy nie). Algosia i Bajtek wygrywają, jeśli zalicytują wartość: \[ W = \left\lfloor \sum_{i=1}^n \frac{\min(a_i, b_i)}{k} \right\rfloor, \] jednocześnie przekazując, że jest to ostateczna zalicytowana wartość. Takich gier w obrębie jednego przypadku testowego będzie \(t = 40\), natomiast wynik będzie zależał od łącznej liczby wygranych gier.

Wartość oczekiwana liczby \(W\)

Zanim przejdziemy do rozwiązywania zadania, zastanówmy się, jak wygląda wartość oczekiwana liczby \(W\). Liczby \(a_i\) i \(b_i\) są niezależnymi zmiennymi losowymi generowanymi z rozkładu jednostajnego na przedziale \([1, m]\). Zatem dla każdego \(1 \leq i \leq n\) mamy: \[ \mathbb{E}[\min(a_i, b_i)] = \sum_{x=1}^m x \cdot \mathbb{P}(\min(a_i, b_i) = x) = \sum_{x=1}^m x \cdot \left( \mathbb{P}(a_i = x, b_i \geq x) + \mathbb{P}(b_i = x, a_i > x) \right) = \] \[ = \sum_{x=1}^m x \cdot \left( \frac{1}{m} \cdot \frac{m - x + 1}{m} + \frac{1}{m} \cdot \frac{m - x}{m} \right) = \sum_{x=1}^m x \cdot \frac{2(m - x) + 1}{m^2} = \frac{2}{m^2} \sum_{x=1}^m (mx - x^2) + \frac{1}{m^2} \sum_{x=1}^m x = \] \[ = \frac{2}{m^2} \left( m \cdot \frac{m(m+1)}{2} - \frac{m(m+1)(2m+1)}{6} \right) + \frac{1}{m^2} \cdot \frac{m(m+1)}{2} = \frac{(m+1)(2m+1)}{6m} \approx \frac{m}{3}. \]

Korzystając z liniowości wartości oczekiwanej, otrzymujemy, że: \[ \mathbb{E}[W] \leq \mathbb{E}\left[ \sum_{i=1}^n \frac{\min(a_i, b_i)}{k} \right] = \frac{1}{k} \sum_{i=1}^n \mathbb{E}[\min(a_i, b_i)] \approx \frac{nm}{3k}. \]

Oznaczmy przez \(S = \sum_{i=1}^n \min(a_i, b_i)\). Rozwiązania wszystkich podzadań będą opierać się na znajdowaniu dokładnej wartości liczby \(S\) za pomocą podbijania stawki. Zauważmy, że jedyna informacja, jaką gracz otrzymuje od partnera, to przyrost licytowanej stawki. Naszą komunikację będziemy zatem opierać na wartościach kolejnych przyrostów. Jeśli protokół komunikacji będzie wymagał zbyt wielu wiadomości lub będzie znacznie zwiększał licytowaną wartość, to obaj gracze zwyczajnie przelicytują wartość \(W\) i przegrają.

Podzadanie pierwsze – \(k = 1\)

Szansa na to, że jakiekolwiek \(a_i\), \(b_i\) będą miały bardzo małe wartości (np. mniejsze niż \(7\)) jest znikoma. Gracze będą po kolei uzgadniać, kto ma mniejszą wartość elementów na danej pozycji dla każdego \(1 \le i \le n\). Obaj gracze utrzymują pomocniczą zmienną \(x\) (początkowo \(x = 0\) dla każdej nowej pozycji), która pełni rolę gwarantowanego dolnego ograniczenia. W swojej turze gracz analizuje swoją liczbę \(v\) na \(i\)-tej pozycji i wykonuje jeden z dwóch rodzajów ruchów:

Jeśli jego liczba \(v \ge x + 7\), to podwyższa licytowaną wartość stawki dokładnie o \(1\). Jest to bezpieczny komunikat dla partnera oznaczający: "moja liczba jest na tyle duża, że możemy szukać dalej". Po tym ruchu obaj gracze po prostu zwiększają \(x\) o \(1\).
W przeciwnym przypadku, jeśli \(v < x + 7\), gracz podwyższa stawkę o wartość \(R = v - x - 1\). Z uwagi na to, że w poprzednich turach partnerzy potwierdzali już posiadanie odpowiednio dużych wartości, przyrost \(R\) wyniesie co najmniej \(2\) i gracz licytujący ma pewność, że jego liczba jest mniejsza niż liczba partnera (bo partner przed chwilą zwiększył stawkę o \(1\), zatem jego liczba jest większa niż \(x + 6\)). Podwyższenie licytowanej stawki o więcej niż jeden jest jednoznacznym sygnałem dla drugiego gracza, że rozstrzygają właśnie tę pozycję. Partner, widząc przyrost \(R\), może z łatwością odtworzyć dokładną wartość minimum na tej pozycji, która wynosi dokładnie \(x + R + 1\). W tym momencie obaj gracze dodają odnalezione minimum do swoich sum i przechodzą do kolejnego indeksu.

Gdy gracze przejdą w ten sposób przez wszystkie \(n\) pozycji, znają już dokładną sumę minimów \(S\). Gracz, na którego przypada kolej, może po prostu obliczyć ostateczny wynik \(W = \lfloor \frac{S}{k} \rfloor\) i zalicytować go, kończąc grę.

Podzadanie drugie – \(n = 10, m = 25\,000, k=200\)

Zauważmy, że Algosia może wysłać swoje liczby dla Bajtka zakodowane w systemie binarnym, rozpoczynając od najbardziej znaczącego bitu. Ustalmy \(1 \le i \le n\). Wówczas, dla każdego \(j \in \{ \lceil \log_2(m) \rceil - 1, \dots, 1, 0 \}\) Algosia może sprawdzić wartość \(j\)-tego bitu w liczbie \(a_i\) oraz podwyższyć stawkę o \(\texttt{wartość bitu} + 1\) (ponieważ musimy licytować ściśle większe wartości, a bity przyjmują wartość \(0\) lub \(1\)). Z kolei Bajtek może zawsze podnosić stawkę o \(1\) i nie przekazywać tym samym żadnej informacji dla Algosi. Bajtek jednocześnie pamięta, jaki bit i z jakiej liczby powinien otrzymać od Bajtosi w jej następnym ruchu. Wówczas, po przesłaniu wszystkich bitów przez Algosię, Bajtek zna cały ciąg \(a\), więc bez problemu może obliczyć wartość \(W\) i ją zalicytować.

Niech \(X\) będzie stawką zalicytowaną przez Algosię i Bajtka tuż przed zakończeniem danej gry. Jest jasne, że gracze są w stanie wygrać wtedy i tylko wtedy gdy \(X \le W\) (w przeciwnym wypadku przelicytowali i już za późno). Oszacujmy wartość oczekiwaną \(X\) w tym przypadku. Ponieważ liczby \(a_i\) są losowane z równym prawdopodobieństwem z przedziału \([1, m]\), to możemy założyć, że również każdy bit niezależnie przyjmuje losową wartość. Niech \(K = \lceil \log_2(nm)\rceil\). Wówczas wartość oczekiwana związana z wysłaniem jednej liczby to około \(K \cdot \frac{1 + 2}{2}\) ze względu na komunikację Algosi (średnio w połowie przypadków dany bit będzie zapalony lub zgaszony) oraz \(K \cdot 1\) dzięki komunikatom Bajtka ("pustym ruchom"). Otrzymujemy sumarycznie, że: \[ \mathbb{E}[X] \approx n \cdot K \cdot \left(\frac{3}{2} + 1\right). \] Z kolei korzystając z uprzednio wyliczonego powyżej wzorku widzimy, że \(\mathbb{E}[W] \approx 417\), z kolei \(\mathbb{E}[X] \approx 375\). Takie rozwiązanie ze sporym zapasem wygrywa prawie wszystkie gry.

Podzadanie trzecie – \(n = 10, m = 25\,000, k=300\)

W poprzednim rozwiązaniu smutny jest fakt, że na każdą wiadomość Algosi przypada podwyższenie stawki przez Bajtka o \(1\), które nic nie wnosi. Nie rezygnujmy jednak całkowicie z pomysłu przesyłania sobie bitów: niechaj gracze podzielą się liczbami po połowie i równolegle przekazują sobie odpowiednie liczby zakodowane binarnie. Przykładowo, Algosia będzie wysyłać Bajtkowi liczby \(a_i\) dla \(i\) parzystych, a Bajtek będzie wysyłać Algosi \(b_j\) dla j\( nieparzystych.

Zauważmy, ze każde z nich będzie chciało przekazać drugiej osobie sumarycznie tyle samo bitów (czyli \(\frac{nK}{2}\)), zatem oboje skończą przekazywanie sobie informacji w tym samym momencie. Zatem nietrudno jest zaimplementować strategię przekazania tych bitów, ponieważ gracze mogą niezależnie od siebie podwyższać stawkę o \(1\) lub o \(2\). Po nadaniu wszystkich swoich wiadomości Algosia i Bajtek patrzą na to, co wysłał im partner. Teraz Algosia wie, jakie są wartości na pozycjach, które nadawał Bajtek i vice-versa. Zatem Algosia wie teraz, ile wynosi \(s_A = \sum_{i=1}^{\frac{n}{2}} \min(a_{2i}, b_{2i})\). Bajtek zna z kolei \(s_B = \sum_{i=1}^{\frac{n}{2}} \min(a_{2i-1}, b_{2i-1})\).

Wystarczy teraz, że Algosia wyśle zakodowaną binarnie wartość \(s_A\) do Bajtka w analogiczny sposób. Bajtek może podwyższać stawkę o \(1\) czekając aż Algosia wyśle mu wszystkie bity \(s_A\). Po otrzymaniu tej informacji, Bajtek zna już wartość \(s_B\) oraz \(s_A\), więc może obliczyć \(S = s_A + s_B\) i zalicytować wartość \(W = \lfloor \frac{S}{k} \rfloor\).

Oszacujmy wartość oczekiwaną \(X\) w tym przypadku. Każdy z graczy wysyła \(\frac{nK}{2}\) bitów, a następnie Algosia wysyła jeszcze \(K\) bitów związanych z wartością \(s_A\). Otrzymujemy, że: \[ \mathbb{E}[X] \approx nK \cdot \frac{3}{2} + K \cdot \left(\frac{3}{2} + 1\right) . \] Z kolei korzystając z uprzednio wyliczonego powyżej wzorku mamy, że \(\mathbb{E}[W] \approx 278\) oraz \(\mathbb{E}[X]\approx 262\), co pozwala na zdobycie pełnej liczby punktów w tym podzadaniu.

Podzadanie szóste – \(k = 4500\)

Sposób I – usprawnienie powyższego rozwiązania

Zauważmy, że w powyższym rozwiązaniu gracze bezmyślnie wysyłają wszystke bity swoich liczb na pozycjach o określonej parzystości. Spójrzmy na sytuację, w której Algosia przesyła bity liczby \(a_1\) do Bajtka w kolejności od najbardziej znaczących bitów. Bajtek w tym czasie wysyła Algosi bity liczby \(b_2\), również w kolejności od najbardziej znaczących bitów. Jednak Bajtek zna również wartość \(b_1\), zatem w pierwszym możliwym momencie, kiedy Algosia wyśle mu \(j\)-ty bit liczby \(a_1\), i będzie się on różnić od \(j\)-tego bitu liczby \(b_1\), to Bajtek może zareagować i poprosić Algosię o zaprzestanie wysyłania bitów liczby \(a_1\). Służyć do tego będzie podwyższenie stawki o \(3\). Wówczas Algosia będzie wiedziała, że Bajtek ma inny \(j\)-ty bit niż ona, zatem jeśli jej \(j\)-ty bit jest równy \(0\), to Bajtek ma \(1\) na tej pozycji, a jeśli jej \(j\)-ty bit jest równy \(1\), to Bajtek ma \(0\) na tej pozycji. W obu przypadkach obaj gracze wiedzą, kto ma mniejszą wartość na tej pozycji. Algosia może zatem przejść do przesyłania bitów liczby \(a_3\) i tak dalej. Symetrycznie Algosia będzie reagować na różniące się bity liczb nadsyłane przez Bajtka.

W tym rozwiązaniu na szczególną ostrożność zasługuje fakt, że ze względu na losowość liczb \(a_i\) i \(b_i\) gracze niekoniecznie w tym samym momencie skończą sobie przesyłać bity. W związku z tym należy mieć specjalny komunikat, który będzie informował drugiego gracza o tym, że skończył on już przesyłać wszystkie bity. Można to zrobić na przykład poprzez podwyższenie stawki o \(4\), a następnie przesyłanie samych "pustych" ruchów powiększających stawkę o \(1\) lub informujących partnera o różniących się bitach, jak opisano powyżej.

Na koniec obaj gracze znowu znają swoje sumy \(s_A\) i \(s_B\), zatem Algosia może wysłać Bajtkowi zakodowaną binarnie wartość \(s_A\) w analogiczny sposób, jak poprzednio, a Bajtek po otrzymaniu tej informacji zna już wartość \(S = s_A + s_B\) i może zalicytować wartość \(W = \lfloor \frac{S}{k} \rfloor\).

Ponownie oszacujmy wartość oczekiwaną \(X\) w tym przypadku. Ustalmy \(1 \le i \le n\). Załóżmy, że Algosia wysyła bity liczby \(a_i\). Zauważmy, że prawdopodobieństwo, że pierwszych \(k\) bitów liczb \(a_i, b_i\) jest takie same, wynosi \(\frac{1}{2^k}\). Zatem prawdopodobieństwo, że Algosia będzie musiała przesłać dokładnie \(j\) bitów, również wynosi \(\frac{1}{2^{j}}\) dla \(1 \le j \le K\) (ponieważ Algosia wyśle te bity liczby \(a_i\), które się zgadzają z bitami liczby \(b_i\) oraz jeden dodatkowy bit, po otrzymaniu którego nastąpi rozstrzygnięcie, kto posiada \(\min(a_i, b_i)\)). Otrzymujemy zatem, że wartość oczekiwana związana z wysłaniem jednej liczby to około: \[ \sum_{j=1}^K \frac{1}{2^j} \cdot j \cdot \frac{3}{2} + 3 \approx 6 \]

Z kolei wartość oczekiwana liczby "pustych" ruchów wynika z różnicy w czasie zakończenia nadawania bitów przez graczy. Bez wchodzenia w matematyczne szczegóły, jest to: \(\sqrt{\frac{4 * n}{\pi}} \approx 35.7\). Intuicyjnie jednak możemy rozumieć, że skoro bity we wszystkich liczbach są losowe, to gracze powinni zazwyczaj kończyć przesyłanie sobie bitów w podobnych momentach.

Zatem wartość oczekiwana związana z przesłaniem wyniku oraz liczby \(s_A\) lub \(s_B\) to: \[ \mathbb{E}[X] = 6n + K \cdot \left(\frac{3}{2} + 1\right) + 35.7 \approx 6102. \] Z kolei korzystając z wyprowadzonego na początku wzoru mamy, że \(\mathbb{E}[W] \approx 6666\) dla \(k=5000\).

Sposób II – wyszukiwanie binarne

Poprzednie rozwiązania przesyłały sobie bity liczby \(a_i, b_i\). Spróbujmy teraz zastosować trochę inne podejście. Niech Algosia i Bajtek wspólnie porozumieją się, kto posiada mniejszą z liczb na indeksie \(i\) przy pomocy wyszukiwania binarnego. Utrzymujmy teraz liczbę \(x\), początkowo równą \(\frac{m}{2}\). Zasada komunikacji jest następująca: Algosia i Bajtek poinformują siebie wzajemnie, czy ich liczba (odpowiednio \(a_i\) lub \(b_i\) jest większa czy nie większa niż \(x\). Niech podniesienie stawki o \(1\) oznacza, że liczba gracza jest ściśle większa niż \(x\), a podniesienie o \(2\) – że jest mniejsza, bądź równa \(x\). Mamy następujące możliwości:

Jeśli suma wzrostów stawki obu graczy to \(3\), to gracz który podniósł stawkę o \(1\) posiada liczbę mniejszą równą \(x\), a więc w konsekwencji liczbę mniejszą niż liczba partnera. Gracze mogą teraz przejść do rozpatrywania liczb na pozycji \(i+1\)-wszej. Taka sytuacja dzieje się z prawdopodobieństwem \(\frac{1}{2}\).
Obaj gracze podnieśli stawkę o \(1\) lub \(2\) jednocześnie. Załóżmy bez straty ogólności ten pierwszy przypadek. Wówczas obaj gracze mają liczby \(a_i, b_i\) ściśle większe niż \(x\). Możemy zatem dla obu graczy jednocześnie zaktualizować przedziały wyznaczające zakresy dla wyszukiwania binarnego i kontynuować taką komunikację dalej.

Oszacujmy ponownie wartość oczekiwaną takiego rozwiązania. Niech \(T\) to zmienna losowa opisująca proces opisany wyżej dla pewnego ustalonego indeksu \(1 \le i \le n\). Wówczas z prawdopodobieństwem \(\frac{1}{2}\) i po podniesieniu stawki o \(3\) proces rozstrzygania właściciela minimum się kończy. W przeciwym przypadku z równym prawdopodobieństwem \(\frac{1}{4}\) stawka rośnie o \(2\) lub o \(4\) i proces jest kontynuowany. Otrzymujemy zatem równanie: \[ \mathbb{E}[T] = \frac{1}{2} \cdot 3 + \frac{1}{4} \cdot (2 + \mathbb{E}[T]) + \frac{1}{4} \cdot (4 + \mathbb{E}[T]), \] skąd już łatwo wynika, że \(\mathbb{E}[T] = 6\). Zatem wartość oczekiwana \(X\) w tym przypadku również wynosi \(6n + K \cdot \left(\frac{3}{2} + 1\right) \approx 6042\), co daje podobne rezultaty do poprzedniego rozwiązania, ale jest znacznie prostsze w implementacji.

Kolejne optymalizacje

Aby zdobyć pełną pulę punktów, Algosia i Bajtek muszą ograniczyć oczekiwany wzrost stawki z \(6n\) do około \(4.5n\) w trakcie pierwszej fazy rozstrzygania, kto ma minimum na każdej pozycji. Można to osiągnąć za pomocą dwóch optymalizacji powyższego rozwiązania z wyszukiwaniem binarnym: łączenia komunikatów oraz zmiany proporcji podziału przedziału wyszukiwania.

Optymalizacja 1 (podzadanie ósme, \(k = 6500\)) – Łączenie wielu komunikatów w jeden

Aby zrozumieć tę optymalizację, prześledźmy standardowy krok wyszukiwania binarnego. Zazwyczaj Algosia sprawdza swoją liczbę względem środka przedziału (oznaczmy go jako \(mid\)) i wysyła tę informację Bajtkowi. Następnie Bajtek sprawdza swoją liczbę względem tego samego \(mid\) i odsyła wynik Algosi. Dopiero po tych dwóch licytacjach oboje w pełni znają wynik, mogą zawęzić przedział i wyliczyć wspólnie nowe, kolejne \(mid\). To oznacza, że wykonywane są dwa licytowania na każdy krok wyszukiwania binarnego.

Zamiast tego, gracze mogą "zazębiać" swoje komunikaty. Załóżmy, że to tura Bajtka. Algosia w swoim poprzednim ruchu przekazała mu już swoją odpowiedź dla aktualnego \(mid\). Bajtek teraz robi dwie rzeczy w ramach jednego ruchu:

Sprawdza własną liczbę względem aktualnego \(mid\). Ponieważ zna już odpowiedź Algosi z poprzedniej tury, ta informacja całkowicie rozstrzyga bieżący krok. Bajtek wie już, jak należy zawęzić przedział i potrafi samodzielnie wyliczyć nowe, następne \(mid'\) dla kolejnego kroku tego wyszukiwania binarnego.
Zamiast czekać na Algosię z wysłaniem odpowiedniej informacji o relatywnej wartości \(a_i\) względem \(mid'\), Bajtek od razu sprawdza swoją liczbę względem nowo wyliczonego \(mid'\).

W swoim ruchu Bajtek koduje więc dwie informacje: swoją odpowiedź dla starego \(mid\) (co pozwala Algosi zaktualizować przedział) oraz swoją odpowiedź dla nowego \(mid'\) (co rozpoczyna od razu nowy krok). Ponieważ każda z odpowiedzi przyjmuje jedną z dwóch wartości (mniejsza-równa lub większa), daje to łącznie 4 kombinacje. Gracz licytuje więc, zgłaszając wzrost stawki o wartość ze zbioru \(\{1, 2, 3, 4\}\).

Gdy Algosia odbierze ten komunikat, odczytuje z niego wynik Bajtka dla starego \(mid\), sama aktualizuje swój przedział, a następnie odczytuje odpowiedź Bajtka dla nowego \(mid'\), co pozwala jej od razu przejść do powyższego punktu 1. Dzięki temu każda pojedyncza licytacja partnera posuwa wspólne wyszukiwanie o jeden pełny krok do przodu!

Oszacowanie wartości oczekiwanej dla pierwszej optymalizacji

Zastanówmy się, jak ta sprytna kompresja komunikatów wpływa na łączny oczekiwany przyrost licytowanej stawki. Ponieważ w standardowym wyszukiwaniu binarnym dzielimy przedział zawsze dokładnie na pół, prawdopodobieństwo, że liczba gracza znajduje się w dolnej połowie (LOWER) wynosi \(\frac{1}{2}\), tak samo jak w górnej (HIGHER).

Skoro oba warianty są zawsze równie prawdopodobne, każda z \(4\) kombinacji zakodowanych w wiadomości gracza ma takie samo prawdopodobieństwo wystąpienia, równe \(\frac{1}{4}\). Oczekiwany wzrost stawki w zaledwie jednym kroku wynosi zatem: \( \frac{1 + 2 + 3 + 4}{4} = \frac{10}{4} = 2.5 \).

Kiedy kończy się przeszukiwanie danego indeksu? Wyszukiwanie dobiega końca dokładnie wtedy, gdy gracze "rozminą" się swoimi odpowiedziami – to znaczy wpadną w przypadek (LOWER, HIGHER) lub (HIGHER, LOWER). Wtedy jednoznacznie wiadomo, kto posiada mniejszą liczbę. Prawdopodobieństwo takiej sytuacji w pojedynczym kroku wynosi \(\frac{1}{2}\).

Skoro szansa na rozstrzygnięcie indeksu w każdym kroku wynosi \(\frac{1}{2}\), to oczekiwana liczba podniesień stawki (zdarzenie losowe \(T\)) możemy obliczyć ze wzoru: \[ \mathbb{E}[T] = 2.5 + \frac{1}{2}\mathbb{E}[T] \implies \mathbb{E}[T] = 5. \]

Zatem łączna wartość oczekiwana \(\mathbb{E}[X] = 5n + \frac{5}{2} K \approx 5042\), podczas gdy dla \(k=6500\) mamy \(\mathbb{E}[W] \approx 5128\), zatem to rozwiązanie z bezpiecznym zapasem wygrywa wszystkie gry w tym podzadaniu.

Druga optymalizacja (i pełne rozwiązanie): asymetryczny podział

W standardowym wyszukiwaniu binarnym wartość \(mid\) ustalamy dokładnie w połowie przedziału. Jednakże, w związku z tym licytowane wartości \(1, 2, 3, 4\) są równie prawdopodobne. A co gdyby zamiast tego, dzielić przedział na dwie części asymetrycznie, aby częściej licytowane były wartości \(1\) i \(2\), a rzadziej \(3\) i \(4\)?

Niech zatem przedział wyszukiwania binarnego będzie dzielony tak, aby obszar LOWER obejmował \(p\%\) przedziału, a obszar HIGHER \((1-p)\%\). Wartość \(p\) dobierzemy później, by zoptymalizować wartość oczekiwaną sumy podwyższeń stawek. Załóżmy, że nasze kodowanie wygląda w następujący sposób:

Przyrost 1: oboje trafili w LOWER. Prawdopodobieństwo takiej sytuacji: \(p^2\).
Przyrost 2: partner w LOWER, gracz w HIGHER. Prawdopodobieństwo: \(p(1-p)\).
Przyrost 3: partner w HIGHER, gracz w LOWER. Prawdopodobieństwo: \(p(1-p)\).
Przyrost 4: oboje trafili w HIGHER. Prawdopodobieństwo: \((1-p)^2\).

Oczekiwany wzrost licytacji w jednym kroku wynosi zatem: \[1 \cdot p^2 + 2 \cdot p(1-p) + 3 \cdot p(1-p) + 4 \cdot (1-p)^2 = 4 - 3p\] Kiedy kończy się porównywanie wartości na danym indeksie? Gdy gracze wpadną w przypadek (LOWER, HIGHER) lub (HIGHER, LOWER). Szansa na to wynosi \(2p(1-p)\). W takim razie oczekiwana suma podniesień stawki do zakończenia przetwarzania jednego indeksu (zdarzenie losowe \(T\)) wynosi: \[\mathbb{E}[T] = 4 - 3p + (1 - 2p(1-p))\mathbb{E}[T] \implies \mathbb{E}[T] = \frac{4-3p}{2p(1-p)},\] co osiąga swoje lokalne minimum na przedziale \([0, 1]\) dla \(p = \frac{2}{3}\). Wtedy \(\mathbb{E}[T] = 4.5\).

Zatem otrzymujemy wtedy, że \(\mathbb{E}[X] \approx 4542\) oraz \(\mathbb{E}[W] \approx 4761\), co pozwala z prawdopodobieństwem bliskim \(1\) zdobyć maksymalną liczbę punktów:)