Question

Имеется три кучи конфет: в первой – 15 конфет, во второй – 17 конфет и в третьей – 37 конфет. Двое коротышек – Незнайка и Знайка – делят конфеты, играя в следующую игру. Они ходят по очереди. За один ход нужно взять одну или две конфеты из каждой кучи (по усмотрению игрока, делающего ход; не обязательно брать одинаковое число конфет из каждой кучи). Если после хода одного из игроков какая-то из куч оказывается разобранной, то другой игрок все оставшиеся в остальных кучах конфеты забирает себе и игра заканчивается. Первым ходит Знайка. Кто из коротышек наберёт больше конфет при условии, что он будет играть наилучшим образом, и как он должен играть, чтобы заведомо набрать больше конфет, независимо от того, как будет играть его соперник?​

Answer 1

Ответ:

Незнайка

Пошаговое объяснение:

Выиграет второй. Его стратегия брать из кучи, где лежит 15 конфет столько, чтобы оставалось количество кратное трем, из двух оставшихся брать по две конфеты.

При такой стратегии после 4 взаимных ходов в первой куче останется 3 конфеты и будет ход Знайки. Сколько бы он конфет не взял (1 или 2)  последнюю заберет Незнайка.

Answer 2

Эта игра имеет определенное решение, которое можно найти с помощью стратегии динамического программирования. Чтобы определить, как Знайка может играть наилучшим образом и набрать больше конфет, независимо от действий Незнайки, давайте посмотрим на ситуацию с конфетами в каждой куче.

Обозначим через P(n1, n2, n3) количество конфет, которое Знайка может гарантированно получить, если в кучах осталось n1, n2 и n3 конфет соответственно. Нашей целью является вычислить P(15, 17, 37), то есть сколько конфет может получить Знайка из начальной позиции.

Рассмотрим, какие ходы может сделать Знайка:

1. Взять 1 конфету из первой кучи, 1 из второй и 1 из третьей.
2. Взять 1 конфету из первой кучи, 1 из второй и 2 из третьей.
3. Взять 1 конфету из первой кучи, 2 из второй и 1 из третьей.
4. Взять 2 конфеты из первой кучи, 1 из второй и 1 из третьей.

Теперь для каждого из этих ходов мы можем выразить P(n1, n2, n3) через значения P для других состояний, которые получаются после хода.

1. P(n1 - 1, n2 - 1, n3 - 1)
2. P(n1 - 1, n2 - 1, n3 - 2)
3. P(n1 - 1, n2 - 2, n3 - 1)
4. P(n1 - 2, n2 - 1, n3 - 1)

Значение P(n1, n2, n3) будет максимумом из этих выражений, так как Знайка будет выбирать тот ход, который позволит ему получить максимальное количество конфет.

Мы можем начать вычисления с низких значений n1, n2 и n3 и последовательно заполнить таблицу значений P для всех возможных состояний. Начнем с P(0, 0, 0), которое равно 0, так как нет конфет для взятия.

Следуя этой логике и вычисляя значения P для всех состояний, в конечном итоге мы сможем найти P(15, 17, 37), то есть количество конфет, которое Знайка может гарантированно получить, играя наилучшим образом.