PrawdopodobieństwoWyzwanieZadanie nr 3886

Wybór najlepszego z dziesięciu kandydatów przy decyzjach podejmowanych na bieżąco

Optymalne zatrzymanie Zadania konkursoweZadania olimpijskie

Dziesięciu kandydatów o różnych (porównywalnych) kwalifikacjach zgłasza się kolejno w losowej kolejności (każda z \(10!\) kolejności jest jednakowo prawdopodobna). Po rozmowie z kandydatem wiemy tylko, jak wypada on na tle wszystkich dotychczasowych, i musimy od razu go przyjąć (kończąc proces) albo odrzucić bezpowrotnie. Wygrywamy, jeśli przyjmiemy najlepszego ze wszystkich dziesięciu. Jakie jest największe prawdopodobieństwo wygranej, jakie można zapewnić odpowiednią strategią?

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Przyjmowanie kogokolwiek, kto nie jest najlepszy wśród dotychczasowych, nie ma sensu. Pokaż, że opłaca się strategia progowa: odrzuć pierwszych \(r-1\) kandydatów, a potem przyjmij pierwszego, który jest lepszy od wszystkich poprzednich. Policz jej skuteczność w zależności od \(r\).

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Kandydata nazwijmy rekordowym, jeśli jest lepszy od wszystkich poprzednich. Przyjęcie kandydata nierekordowego daje przegraną. Rekordowy kandydat numer \(i\) jest najlepszy ogółem z prawdopodobieństwem \(\frac{i}{10}\) (najlepszy z pierwszych \(i\) jest najlepszym ogółem z tym prawdopodobieństwem), niezależnie od przebiegu wcześniejszych rozmów.
  2. Niech \(U_i\) będzie największą szansą wygranej, gdy odrzuciliśmy pierwszych \(i\) kandydatów; \(U_i\) nie rośnie z \(i\) (kto ma więcej możliwości, może naśladować strategię późniejszą). Przy rekordowym \(i\)-tym kandydacie opłaca się go przyjąć, gdy \(\frac{i}{10}\ge U_i\); lewa strona rośnie, prawa nie rośnie — więc optymalna jest strategia progowa z pewnym progiem \(r\).
  3. Strategia z progiem \(r\ge2\) wygrywa, gdy najlepszy stoi na pozycji \(i\ge r\), a najlepszy spośród pierwszych \(i-1\) stoi wśród pierwszych \(r-1\): \(P(r)=\sum_{i=r}^{10}\frac1{10}\cdot\frac{r-1}{i-1}=\frac{r-1}{10}\sum_{i=r}^{10}\frac{1}{i-1}\) (dla \(r=1\) mamy \(P=\frac1{10}\)).
  4. Różnica \(P(r+1)-P(r)=\frac1{10}\Bigl(\sum_{j=r}^{9}\frac1j-1\Bigr)\) jest dodatnia dla \(r\le3\) (bo \(\frac13+\ldots+\frac19>1\)) i ujemna dla \(r\ge4\) (bo \(\frac14+\ldots+\frac19<1\)). Maksimum daje więc \(r=4\) (\(P(3)\approx0{,}366\), \(P(4)\approx0{,}399\), \(P(5)\approx0{,}398\)).
  5. \(\frac13+\frac14+\ldots+\frac19=\frac{3349}{2520}\), więc największe prawdopodobieństwo to \(\frac{3}{10}\cdot\frac{3349}{2520}=\frac{3349}{8400}\).

Odpowiedź: \(\frac{3349}{8400}\)

Czego warto się nauczyć?

Klasyczne prawdopodobieństwo sprowadza się do dobrego policzenia dwóch zbiorów: wszystkich wyników i wyników sprzyjających.

Więcej zadań z prawdopodobieństwa →

Podobne zadania