Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу один камень (действие А) или утроить количество камней в куче, а затем добавить ещё один камень (действие Б). Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 31 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится более 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 32 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 31. Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна

Answer 1

Ответ:

4

Объяснение:

Зная, что изначально в куче было S камней, для победы нужно получить не менее 32, рассмотрим все возможные ходы Пети, при которых он не выиграет. Чтобы Петя не выиграл, после любого его хода в куче должно получиться меньше 32 камней.

Действие А) S+1<32, тогда S<32-1=31

Действие Б) 3*S+1<32, тогда S<(32-1)/3=11

А теперь распишем ходы Вани. Чтобы точно победить, Ване нужно действовать так, чтобы получить максимальный результат - из двух действий максимальный дает действие Б. После его хода в куче должно стать или 32 камня, или больше.

Действие А) 3*(S+1)+1=3*S+4>=32, тогда S>=(32-4)/3=10

Действие Б) 3*(3*S+1)+1=9*S+4>=32, тогда S>=(32-4)/9=4

Таким образом мы понимаем, что нужное для Ваниной победы первым ходом число S должно должно лежать в диапазоне от 4 до 31, тогда минимальным подходящим будет 4. Проверим:

Случай 1. Петя ходит действием А. 4+1=5. Ваня ходит действием Б. 5*3+1=16. Ваня не выиграл.

Случай 2. Петя ходит действием Б. 3*4+1=13. Ваня ходит действием Б. 13*3=39. Ваня выиграл.

Несмотря на то, что если Петя пойдет действием  А, Ваня не выиграет, его победа всё равно возможна, если тот пойдет действием Б. А нас именно о случае, когда она возможна, и спрашивают.

Чтобы убедиться в верности рассуждений, проверим, нельзя ли взять еще меньшее число - 3:

Случай 1. Петя ходит действием А. 3+1=4. Ваня ходит действием Б. 3*4+1=13. Ваня не выиграл.

Случай 2. Петя ходит действием Б. 3*3+1=10. Ваня ходит действием Б. 3+10+1=31. Ваня не выиграл.

Таким образом, мы выяснили, что минимальным начальным количеством камней, когда возможна победа Вани первым ходом, является 4.

Answer 2

Давайте рассмотрим эту задачу, начиная с самых маленьких значений S и постепенно увеличивая его, чтобы найти минимальное значение S, при котором Ваня выигрывает первым ходом после неудачного первого хода Пети.

1. Если S = 1, то Петя может добавить 1 камень и оставить Ваню с 2 камнями. Ваня утроит количество камней и добавит еще 1, чтобы получить 6 камней, и Петя уже выигрывает следующим ходом, увеличив количество камней до 7. Таким образом, это не минимальное значение S.

2. Если S = 2, то Петя может добавить 1 камень и оставить Ваню с 3 камнями. Ваня утроит количество камней и добавит еще 1, чтобы получить 7 камней, и Петя уже выигрывает следующим ходом, увеличив количество камней до 8. Таким образом, это тоже не минимальное значение S.

3. Если S = 3, то Петя может добавить 1 камень и оставить Ваню с 4 камнями. Ваня утроит количество камней и добавит еще 1, чтобы получить 10 камней. Теперь у Пети есть выигрышная стратегия. Он может добавить 1 камень, чтобы получить 11 камней, и затем каждый раз повторять ход Вани, утраивая количество камней и добавляя 1. В этом случае Петя всегда будет иметь ответ, чтобы оставаться в игре и никогда не допустит, чтобы в куче оказалось 32 или больше камней.

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