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

Обозначим через 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 ходов