Олимпиадная задача про Петю и Васю: Определение числа по сумме цифр, 8-9 класс

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

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