Поиграйте на досуге

[spamsink]

Рассмотрим игру: каждый из двух игроков в секрете от другого пишет на листке бумаги целое положительное число. Потом листки открываются и числа сравниваются; если они равны, то в этом раунде фиксируется ничья. Тот, чье число меньше как минимум на 2, выигрывает 1 буказоид; если же числа отличаются на 1, то тот, чье число больше, выигрывает 2 буказоида.

Интуитивно, чему равно минимальное число, которое заведомо нет смысла использовать? Потом проверьте себя.

Comments

[maksa.livejournal.com]

Я, наверное, совсем плох, но интуитивно число не угадывается, а попытки себя проверить вроде бы приводят к тому, что 6 называть почти никогда не приходится. 5 редко, но приносит пользу.

[janatem.livejournal.com]

Наивный ответ, видимо, такой: глядя на таблицу выигрышей, видим, что сточка для единицы имеет лишнюю клеточку +2 по сравнению со строчкой для двойки, поэтому делаем вывод, что двойка мажорирует единицу. Но потом оказывается, что после вычеркивания единицы столь же «плохой» становится двойка, и т.д.

В общем, интуиция здесь отказывается работать, так что надо в лоб искать оптимальную стратегию: построить такое распределение своих чисел, чтобы для любого распределения соперника выигрыш был одним и тем же (по-моему, это универсальное решение максимина для конечных таблиц, не знаю, сработает ли для бесконечной).

[spamsink]

Логично пробовать таблицы увеличивающегося размера и смотреть, сходится ли. Оказывается, да, и довольно быстро.

[janatem.livejournal.com]

Но я и с бесконечной справился. Получается система уравнений с бесконечной ленточной матрицей, которая в лоб решается прогонкой. Странное дело, если я не проврался в вычислениях, то двойку надо брать реже чем единицу.

Правда, метод недостаточно обоснован — не факт, что в бесконечном случае оптимум достигается именно при таких условиях.

[spamsink]

Нет, двойку надо брать чаще, чем единицу. Так начиная с какого числа вероятности равны нулю?

[janatem.livejournal.com]

Про двойку я оговорился, имел в виду, что тройка лучше двойки, что меня удивило. Точнее, первые несколько компонент распределения (без нормировки!) таковы: 1, 2/3, 10/9.

Дальше я считать прогонкой устал, тем более, что закономерности так просто не увидишь. Вместо этого составил реккурентное уравнение: 3*p(n)-2*p(n+1)-2*p(n+2)+3*p(n+3)=0 с вышеуказанными начальными значениями. Корни характеристического уравнения все различные и равны по модулю единице, что хорошо, поскольку последовательность не разойдется к бесконечности.

С другой стороны, остаются две проблемы:
1. Непонятно, что делать с отрицательными значениями (а таковые будут, см, ниже). Можно, конечно, заменить их нулями, но у меня и так проблемы с обоснованием метода, а станет еще сложнее.
2. Почти наверно будет проблема с нормировкой, поскольку последовательность скорее всего не суммируется, и, более того, ее члены к нулю не стремятся.

В какой-то момент я заколебался считать вручную и засунул реккурентную формулу в альфу (http://www.wolframalpha.com/input/?i=3*f%28n%29-2*f%28n%2B1%29-2*f%28n%2B2%29%2B3*f%28n%2B3%29%3D0%2C+f%281%29%3D9%2C+f%282%29%3D6%2C+f%283%29%3D10), после чего увидел, что отрицательные значения точно есть.

[spamsink]

Если заколебаться считать вручную, то можно воспользоваться Nash equilibrium solver.