Теория игр — решение заданий

📌 Задание:

Петя и Ваня играют в камни, есть 2 кучи камней. За один ход игрок может добавить в любую кучу один камень или добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается, когда суммарное количество камней будет не менее 58. В начальный момент было 6 камней, во второй куче S камней.

В #19 необходимо назвать минимальное значение, при котором Ваня выиграет первым ходом после хода Пети.

✍️ Выпишем все возможные ходы Пети: 6+S; S, 6+1;S, 6; S+1, 6: S+6. Выгодный ход для Вани — сходить по максимальному: увеличить минимальную кучу камней на максимальную. И эти значения должны удовлетворять условию выигрыша: >=58.

2(6+S)+S>=58
2S+7>=58
2S+6>=58
2(S+6)+6>=58

и выберем минимальное, S=16

👾 Перед #20, в котором нужно найти два значение, при которых у Пети есть выигрышная стратегия, причем Петя не может гарантированно выиграть за один ход.
Выигрышные ходы мы берем из предыдущего пункта, например это: 22;16+, 22;15+, 21;16+, 25;8+.

🌳Тогда распишем дерево ходов в выигрышные позиции. В позицию 21;16 мы можем попасть из позиции 21;15 Пети (то есть был сделан ход увеличить кол-во камней в меньшей кучи на большее кол-во),а также из 21;15 мы попадем в другие выигрышные позиции: 22;15,21; 36, и 36;15. Тогда начальное значение = 6; 15.

🔍 Необходимо найти и второе значение: например, в выигрышную позицию 8;25 можно попасть из позиции 7;25, также мы попадем в другие выигрышные для Пети позиции: 7;26, 7;32, 32;25 — тогда начальное значение = 6; 25