Победитель данной игры

Question

Алиса и Боб играют в игру. Им было дано n (<50) чисел, которые лежат между 1-1000. За один ход они могут сделать одно из следующих
1. Уменьшение числа на 1.
2. Сотрите 2 числа и напишите их сумму.
Число при достижении 0 автоматически стирается. Игрок проигрывает, если он не может сделать ни одного из 2 ходов. Учитывая, что Алиса играет первой, как мы можем сказать, кто победит в игре, если оба будут играть оптимально?

Можно ли решить этот вопрос, если не знать алгоритмы теории игр?

Answer 1

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

Предположим, что числа в начале игры: x ₁, x ₂, x ₃,..., x _n. Обратите внимание, что только ход 1 когда-либо изменяет общую сумму всех n номера. Таким образом, мы сразу знаем, сколько раз Алиса и Боб совершат 1 ход в общей сложности.

Однако количество раз, которое они делают ход 2, не является постоянным. Чтобы проанализировать, сколько раз это произойдет, обратите внимание, что ход 2 и стирание 0 терминов - это единственные вещи, которые уменьшают количество написанных чисел. Таким образом, два из них будут происходить в общей сложности n раз между ними, и по крайней мере один 0 должен быть удален (когда последний декремент сделан).

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

• Предполагая, что вы уже знаете соотношение чисел, кто в порядке, если вы продолжаете делать только первый ход, и кому нужен второй ход, чтобы выиграть?
• Каково соотношение n связано с вышеизложенным? (Обратите внимание, как меняется динамика, когда кто-то делает ход 2)

В любое время, когда одно из чисел равно 1, вы можете поспорить, что будет много размышлять о том, уменьшать его или нет (или стирать 0), или выбрать его в качестве одного из двух чисел, которые будут заменены на сумма. Это решение будет напрямую связано с вышеуказанными пунктами.

Наконец, если движение "должно произойти", какая будет разница между "сделать этот шаг как можно скорее" и "остановиться до последнего возможного момента, чтобы сделать этот шаг"?