Форум умных людей

Любопытно узнать - на много ли шансы мудреца на успех больше 1/100? Многие предлагают следующую стратегию: пропустить первую половину билетов и затем выбрать первую сумму, превосходящую все предыдущие, если таковая найдется. Это достаточно разумно, но такая стратегия не является оптимальной. Очень немногие представляют себе порядок величины вероятности выйграша.
Мы начнем с рассмотрения нескольких примеров. Поскольку мы ничего не знаем о суммах, проставленных неа билетах, то мы можем рассматривать лишь номера билетов при их упорядочивании согласно величинам сумм, записанных на них. Если, например, у нас имеется три билета с номерами 1 2 3, то билету 3 отвечает наибольшее приданое. Для одного или двух билетов задача тривиальна: мудрец делает правильный выбор при одном билете, и его шансы на выйграш равны 1/2 при двух билетах.
ПРи трех билетах имеем шесть возможных способах вытаскивания:
123   231*
132*   312
213*   321
Одна из стратегий - пропустить первый билет и затем выбрать первый номер, его превосходящий, если такой найдется. Эта стратегия выигрывает в трех случаях, отмеченных звездочкой, т. е. в половине всех возможных случаев, что значительно улучшает просто слуцчайную догадку, например, выбор первого билета.
Допустим теперь, что у нас четыре билета. Их возможные перестановки есть:
1234      2134       3124*+    4123
1243+    2143*+   3142*+    4132
1324+    2314+     3214*+    4213
1342+    2341+     3241*+    4231
1423*    2413*      3412*      4312
1432*    2431*      3421*      4321
Кажется разумным пропустить первый билет и остановиться на следующем наибольшлем номере, если он есть. Назовем этот план стратегия 1.Звездочки в нашем списке указывают на случай выйграша этой стратегии. Вероятность правильного решения равна здесь 11/24, что гораздо лучше, чем случайное решение с вероятностью выйграша 1/4.
Стратегия 2. пропускает первые два номера и затем выбирает первый номер, их превосходящий, 10 перестановок, в которых эта стратегия дает выйграш, отмечены крестиком. Видно, что стратегия 1, выигрывает чаще.
Если продолжать изучение всех возможных случаев их перечеслением, то задача приобретает зловещий вид, так как уже для восьми билетов число перестановок 40320. Далее, могут существовать хорошие стратегии, которые мы упустим из виду, хотя это кажется невероятным. Будем надеяться, что математика сможет нам помочь.
  Следует подчеркнуть, что мудрец ничего не знает о распределении номеров, чтобы удостовериться в этом, король может сам вытаскивать билеты и сообщать мудрецу их номера среди уже появившехся. Только билет с наибольшим преданным заслуживает внимания; назовем такое преданое максимальным.
Покажем теперь, что оптимальная стратегия - пропустить s-1 билетов и выбрать первый максимальный номер среди среди них. Мы выберем максимальное приданое на i-м шагу, если вероятность того, что оно наибольшее среди всех имеющихся, превосходит вероятность правильного решения при оптимальной стратегии и более позднем вытягивании. Формально: остановимся на максимальном номере при i-м вытягивании, если
P ( выйграть при i-м вытягивании) > Р ( выйграть при оптиматльной стратегии, начиная с i+1 вытягивания).  (1)
Покажем, что вероятность, в правой части (1) убывает, когда i- возрастает, а веоятность в левой части (1) возрастает с возрастанием i, и потому существует выбор шага i, после которого предпочтительнее удержать максимальное приданое, нежели продолжать испытания. Вычисляя затем вероятность выйграша для такой стратегии, найдем оптимальный выбор занчения s/
После нескольких первых ходов в этой игре мы можем еще прибегнуть ко всем стратегиям, определяемым последующими вытаскиваниями, так как мы всегда можем пропустить часть билетов, пока не достигнем нужного нам числа билетов. Следовательно, вероятность в правой части неравентсва (1) не возрастает с ростом i. При i=0 это искомая оптимальная вероятность, а при i=n-1 эта вероятность равна 1/n как вероятность выйграша при выборе на последнем шагу.
Вероятность того, что на i-м шагу максимальное приданое больше всех имеющихся, равна вероятности того, что наилучший номер находитяся на одном из первых i билетов, а именно равна i/n, что является строго возрастающей от 1/n до 1 фунцией от i.
Поэтому значеие i/n в какой-то точке превосходит вероятность выйграша при продолжении испытаний. Таким образом, оптимальная стратегия может быть задана следующим правилом: пропустить s-1 первых номеров и выбрать затем первого лидера, т. е. первый номер, который больше всех предыдущих. Сосчитаем вероятность выйграша для такой стратегии. Вероятнос правильного решения есть вероятность появления ровно одного лидера между s-м шагом и n-м шагом. Вероятность того, что наилучший билет появился на к-v шагу, равна 1/n. Вероятность того, что максимум к-1 номеров появился среди первых s-1 номеров, есть (s-1)/(к-1). Произведение (s-1)/[n(к-1)] дает вероятность того, что мы выйграем при выборе к, s<=k<=n. Суммируя эти числа, получим вероятность п(s,n) получения наилучшего приданного при оптимальной стратегии:
            1   n      s-1       s-1     n-1    1          s-1        1      1            1
п(s,n)=---  Е    -------=--------   Е     ----  =  -------( ----- + -----+...+  -----)? 1<=s<=n. (2)
           n  к=s   k-1        n      к=s-1  к           n      s-1      s             n-1
Так как первое вытаскивание всегда дает максимальный номер, то п(1,n)=1/n. Заметим, что при n=4, s=2 имеем п(2,4)=11/24, как и в нашем примере.
Оптимальное значение s, скажем s*, есть минимальное s, для которого имеет место неравенство (1), т. е. это наименьшее s, для которого
 s                   s       1         1             1
--->п(s+1,n)=----( ---- +  -----+...+ ------)  (3)
n                    n       s       s+1           n-1

или, что равносильно, такое s, для которого
 
   1     1              1            1        1         1              1
----+------+...+ ------<1< ------+ ----- +  -----+....+ -----   .   (4)
 s     s+1           n-1           s-1        s       s+1           n-1

Оптимальное значение s и вероятности выйграша при разных n:
n        s              п (s,n)          n         s      п (s,n)
1        1              1,000          10        4      0,399
2        2              0,500          20        8      0,384
3        2              0,500          50        19    0,374
4        2              0,458          100      38     0,371
5        2              0,433          беск.    n/e    1/е≈0,368

Эта таблица дает оптимальные значения s и соответствующие им вероятности правильного решения для небольших значений n. Для n=100 следует пропустить 37 приданных и выбрать после этого первое максимальное.