Задача про монеты и две чаши.
Два игрока играют в игру:
Есть две чаши, в каждую из которых помещается любое количество монет. Первый игрок кладет в первую чашу любое количество монет на свой выбор. После этого второй игрок, зная сколько монет положил первый, кладет во вторую чашу любое количество монет на свой выбор. После этого, начиная с первого игрока, каждый игрок совершает один из трех возможных ходов:
1. Взять любое количество монет из первой чаши
2. Взять любое количество монет из второй чаши
3. Взять одинаковое количество монет из обеих чаш
Оба игрока знают, сколько монет лежит в чашах в каждый момент времени. Побеждает тот игрок, после хода которого в обоих чашах не останется монет. Существует ли стратегия, гарантирующая победу, Если существует, то опишите эту стратегию.
Не факт, но очень похоже, что так:
Предлагается разбить всё множество неотрицательных чисел на пары так:
(0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) ...
то есть:
-начать с (0,0)
-в качестве первого числа брать наименьшее из ранее не включенных в другие пары
-разность между вторым и первым должна быть на 1 больше, чем у предыдущей пары.
Игрок №2 своим первым ходом всегда сможет создать ситуацию, соответствующую паре из списка. Игрок №1, взяв монеты, гарантированно создаст ситуацию "не из списка" - это довольно очевидно. Сложнее (но, по-видимому, можно) доказать, что И№2 после этого своим ходом всегда вновь сможет создать ситуацию "из списка". Тогда И№1 победить не сможет, а И№2, наоборот, когда-то создает (0,0), поскольку перебирает пары из списка в порядке убывания (непоследовательно).
Тут еще доказывать и доказывать, но очень похоже, что как-то так.)