теория-вероятностей - Помогите найти самую оптимальную стратегию игры

Итак, я буду рассматривать задачу в такой постановке. Компьютер с равной вероятностью загадывает какое-то число от $%1$% до $%n$%. Игрок называет какое-то число, и компьютер отвечает на вопрос, верно ли, что названное число больше загаданного. То есть он отвечает "нет", если названное число меньше загаданного или равно ему. Игроку присуждается победа (не важно, кем именно) ровно в тот момент, когда по имеющейся у него информации загаданное число определяется однозначно.

Дадим ответ на вопрос, какая стратегия является оптимальной при каждом $%n$% от $%1$% до $%9$%, и сколько в среднем потребуется задать вопросов для победы. Это число вопросов обозначим через $%f(n)$%, и покажем, как эти числа последовательно найти.

Прежде всего, ясно, что $%f(1)=0$%. Далее, если $%n=2$%, то надо назвать число $%2$%, что позволит однозначно узнать, какое число загадано. Если компьютер скажет "да", то загадана единица, а если "нет", то загадана двойка.

Теперь пусть $%n=3$%. Ясно, что называть число $%1$% бессмысленно из-за предсказуемого ответа "нет". Если названо $%2$%, то с вероятностью $%1/3$% компьютер ответит "да", и тогда мы за один ход угадали число $%1$%. Но с вероятностью $%2/3$% ответ будет "нет", если загадано $%2$% или $%3$%. Тут нам потребуется ещё один ход, чтобы угадать, какое именно из этих двух чисел загадано. То есть всего здесь потребуется два хода. Среднее число ходов для угадывания будет равно $%(1/3)\cdot1+(2/3)\cdot2=5/3$%. Легко понять, что то же самое произойдёт, если мы назовём число $%3$%. С вероятностью $%1/3$% ответ будет "нет" (если загадано $%3$%), и с вероятностью $%2/3$% будет сказано "да" (если загадано $%1$% или $%2$%). Эта ситуация полностью симметрична предыдущей. Таким образом, $%f(3)=5/3$%, а стратегия состоит в том, что называть надо $%2$% или $%3$%.

Удобно далее каждое из чисел $%f(n)$% представить в виде дроби $%g(n)/n$% (она в каких-то случаях может оказаться сократимой, но это не важно). И далее мы будем следить не за дробями, а за числами вида $%g(n)$%. На данный момент мы знаем, что $%g(1)=0$%, $%g(2)=2$%, $%g(3)=5$%. Заметим также, что если мы знаем стратегию и среднее число ходов для угадывания числа от $%1$% до какого-то $%m$%, то мы знаем то же самое для любых $%m$% последовательных натуральных чисел. Это значит, что если компьютер загадывает число от $%6$% до $%8$% включительно (с той же равной вероятностью), то это ничем не отличается от задачи с числами $%1$%, $%2$%, $%3$%.

Найдём числа $%f(4)$% и $%g(4)$%, после чего станет ясна общая закономерность. Пусть игрок назвал число $%k+1$%. Тогда все числа можно разделить на те, которые меньше $%k+1$% -- их имеется ровно $%k$%, и все остальные, которых имеется $%n-k$%. Ясно, что с вероятностью $%k/n$% компьютер загадал одно из $%k$% чисел, и в этом случае ответ будет "да", а с вероятностью $%(n-k)/k$% он загадал одно из $%n-k$% чисел, и тогда ответ будет "нет". После ответа игроку надо будет угадать либо одно из $%k$% идущих подряд чисел, что в среднем требует $%f(k)$% ходов, либо одно из $%n-k$% последовательных чисел, что в среднем требует $%f(n-k)$% ходов. Во всех случаях сохраняется равная вероятность того, что загадано одно из последовательных чисел определённого диапазона. Таким образом, когда мы называем число $%k$%, то нам в среднем потребуется для угадывания сделать $%1+(k/n)f(k)+((n-k)/n)f(n-k)$% ходов (первое слагаемое учитывает тот ход, который мы только что сделали). Мы при этом должны подобрать такое $%k < n$% (напомним, что называемое игроком число мы обозначили через $%k+1$%), чтобы полученное среднее значение оказалось минимальным. Оно и будет равно $%f(n)$%, а число $%g(n)$% будет в $%n$% раз больше, и потому оно будет равно минимальному значению выражения $%n+kf(k)+(n-k)f(n-k)=n+g(k)+g(n-k)$%. Таким образом, имеет место следующая рекуррентная формула: $$g(n)=\min\limits_{k < n}\,(g(k)+g(n-k)),$$ и стратегия будет состоять в выборе числа $%k$%, на котором достигается этот минимум. (Вообще говоря, оно может принимать не единственное значение.)

Итак, при $%n=4$% мы рассматриваем найденные ранее числа $%g(1)=0$%, $%g(2)=2$%, $%g(3)=5$%, и далее сравниваем значения сумм $%g(1)+g(3)=5$%, $%g(2)+g(2)=4$%. Вот втором случае значение является наименьшим, и это значит, что называть надо число $%3$%, и при этом $%g(4)=4+g(2)+g(2)=8$%, а $%f(4)=8/4=2$%. Иными словами, одно из четырёх загаданных чисел в среднем будет угадываться два хода.

Далее действует по описанному алгоритму. Для нахождения $%g(5)$% выпишем уже найденные числа вида $%g(n)$%, то есть $%0,2,5,8$%. Суммы, которые надо сравнивать -- это $%0+8$% и $%2+5$%. Второе из значений меньше, и это значит, что надо называть или $%3$%, или $%4$%. После чего с вероятностью $%2/5$% нам надо будет угадать одно число из двух, и с вероятностью $%3/5$% одно число из трёх. Теперь надо не забыть прибавить $%n=5$%, и получить $%g(5)=5+2+5=12$%.

Далее этот способ приводит к таким равенствам: $%g(6)=6+2+8=6+5+5=16$% (здесь можно называть любое число от $%3$% до $%5$%); $%g(7)=7+5+8=20$% (называть надо $%4$% или $%5$%), $%g(8)=8+8+8=24$% (называем $%5$%), и, наконец, осталось найти $%g(9)$%. У нас к этому времени найдены числа $%0,2,5,8,12,16,20,24$%, и минимальная сумма чисел, равноотстоящих от концов, равна $%g(4)+g(5)=8+12=20$%, то есть называть надо число $%5$% или $%6$%, при котором $%9$% чисел разбиваются на две группы с количеством $%4$% и $%5$% (так, если мы назвали $%6$%, то в одной группе числа от $%1$% до $%5$%, а в другой -- от $%6$% до $%9$% в количестве $%4$% штук). Итого мы имеем здесь $%g(9)=9+20=29$%, и $%f(9)=29/9$%, то есть число от $%1$% до $%9$% угадывается в среднем за такое количество шагов, приблизительно равное $%3,222...$%.

Можно установить некую общую закономерность для этой последовательности, и найти её значения для каких угодно $%n$%.

Будет хорошо, если я решил именно ту задачу, которая имелась в виду. Мне она весьма понравилась.