?

Log in

No account? Create an account

Поиграйте на досуге - Общество дровосеков Бердичева по изучению Мишны

Dec. 9th, 2014

04:30 pm - Поиграйте на досуге

Previous Entry Share Next Entry

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

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

Comments:

[User Picture]
From:maksa
Date:December 10th, 2014 01:46 am (UTC)
(Link)
Я, наверное, совсем плох, но интуитивно число не угадывается, а попытки себя проверить вроде бы приводят к тому, что 6 называть почти никогда не приходится. 5 редко, но приносит пользу.
(Reply) (Thread)
[User Picture]
From:janatem
Date:December 10th, 2014 02:44 pm (UTC)
(Link)
Наивный ответ, видимо, такой: глядя на таблицу выигрышей, видим, что сточка для единицы имеет лишнюю клеточку +2 по сравнению со строчкой для двойки, поэтому делаем вывод, что двойка мажорирует единицу. Но потом оказывается, что после вычеркивания единицы столь же «плохой» становится двойка, и т.д.

В общем, интуиция здесь отказывается работать, так что надо в лоб искать оптимальную стратегию: построить такое распределение своих чисел, чтобы для любого распределения соперника выигрыш был одним и тем же (по-моему, это универсальное решение максимина для конечных таблиц, не знаю, сработает ли для бесконечной).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 10th, 2014 09:25 pm (UTC)
(Link)
Логично пробовать таблицы увеличивающегося размера и смотреть, сходится ли. Оказывается, да, и довольно быстро.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:December 10th, 2014 09:39 pm (UTC)
(Link)
Но я и с бесконечной справился. Получается система уравнений с бесконечной ленточной матрицей, которая в лоб решается прогонкой. Странное дело, если я не проврался в вычислениях, то двойку надо брать реже чем единицу.

Правда, метод недостаточно обоснован — не факт, что в бесконечном случае оптимум достигается именно при таких условиях.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 10th, 2014 09:47 pm (UTC)
(Link)
Нет, двойку надо брать чаще, чем единицу. Так начиная с какого числа вероятности равны нулю?
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:December 11th, 2014 09:01 am (UTC)
(Link)
Про двойку я оговорился, имел в виду, что тройка лучше двойки, что меня удивило. Точнее, первые несколько компонент распределения (без нормировки!) таковы: 1, 2/3, 10/9.

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

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

В какой-то момент я заколебался считать вручную и засунул реккурентную формулу в альфу, после чего увидел, что отрицательные значения точно есть.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 11th, 2014 04:03 pm (UTC)
(Link)
Если заколебаться считать вручную, то можно воспользоваться Nash equilibrium solver.
(Reply) (Parent) (Thread)