Question

Вася и Петя играют в следующую игру. Они по очереди берут яблоки из корзины, не меньше 1 и не более 7 каждый раз. На каждом ходу игроку нельзя брать столько же яблок, сколько только что взял соперник (по количеству). Проигрывает тот, кто не сможет сделать ход. В начале игры в корзине было 15 яблок. Первым ходит Вася. Сколько яблок он должен взять, делая первый ход, чтобы гарантировано выиграть игру?

Answer 1

Обозначим через S(n) сумму цифр числа n.

  Алгоритм. Первым ходом Вася называет 1. Если число x оканчивается на k нулей, то  S(x – 1) = 2011 + 9k.  Таким образом Вася узнаёт положение самой правой ненулевой цифры в x. Положим  x1 = x – 10k.  Вася знает, что  S(x1) = 2011.  Подобрав на втором ходу число a так, что  x – a = x1 – 1,  Вася узнаёт сколько нулей в конце x1. Пусть их m. Положим  x2 = x1 – 10m.  Тогда  S(x2) = 2010.  Подобрав на третьем ходу число a так, что 
x – a = x2 – 1,  Вася узнаёт сколько нулей в конце x2, и т. д. После 2012 хода он получит  S(x2012) = 0,  тем самым найдя x.

  Оценка. Пусть Петя признался, что в записи x есть только нули и единицы, то есть  x = 10k2012 + 10k2011 + ... + 10k1,  где  k2012 > k2011 > ... > k1.  При этом задача Васи сводится к выяснению значений показателей ki. Пусть Васе не везёт, и на i-м ходу оказывается, что 10ki больше предъявленного Васей числа a. Тогда, независимо от значений k2012, ...,  ki+1,  S(x – a) = S(10ki – a) + (2012 – i).  Тем самым, о значениях  k2012, ..., ki+1  ничего не известно (кроме того, что все они больше ki). В частности, после 2011 ходов может остаться неизвестным точное значение k2012.


Ответ 2012ходов

Answer 2

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

Изначально в корзине 15 яблок. Вася должен выбрать количество яблок так, чтобы оставить Пете число яблок, которое обязательно приведет к поражению Пети на следующем ходу, независимо от его действий. Для этого Васе нужно выбрать такое количество яблок, чтобы оставить в корзине 8, 9 или 10 яблок.

Вот почему:

• Если Вася возьмет 7 яблок (оставив 8), то Петя сможет взять от 1 до 7 яблок и оставить Васе 1 яблоко, что гарантированно приведет к поражению Васи на следующем ходу.
• Если Вася возьмет 6 яблок (оставив 9), то Петя может взять 1 яблоко и оставить Васе 8 яблок. Таким образом, Петя победит на следующем ходу.
• Если Вася возьмет 5 яблок (оставив 10), то Петя может взять от 1 до 4 яблок и оставить Васе 6-9 яблок. В этом случае Петя также победит на следующем ходу.

Итак, Васе следует взять 4 яблока в своем первом ходе (оставив 11 в корзине). Это позволит ему контролировать ситуацию и гарантировать свою победу в игре.