Решение задачи 505

Условие:

Сергей Дурасов утверждает, что придумал 1000-значное число, делящееся на 2¹⁰⁰⁰, в записи которого участвуют только цифры 1 и 2. Не лукавит ли он?

Решение:

Докажем по индукции следующее утверждение: длю любого натурального n найдется n-значное число, состоящее только из единиц и двоек, делящееся на 2ⁿ.

База: 2 делится на 2 (n = 1).

Переход:
пусть есть n-значное число А, которое кратно 2ⁿ, состоящее лишь из 1 и 2. Если А делится на 2ⁿ⁺¹, то можно к числу А слева дописать двойку. Тогда новое число будет (n+1)-значным, будет состоять только из единиц и двоек и будет делиться на 2ⁿ⁺¹, так как оно будет равно 2 * 10ⁿ + A (каждое слагаемое делится на 2ⁿ⁺¹).

Если же А не делится на 2ⁿ⁺¹, то допишем к А слева единицу. Почему это число будет делиться на 2ⁿ⁺¹? Так как А не делится 2ⁿ⁺¹, но делится на 2ⁿ (по предположению индукции), то оно имеет вид А = 2ⁿ * k, где k -- нечетное. Новое число имеет вид 10ⁿ + A = 2ⁿ5ⁿ + 2ⁿ * k = 2ⁿ(5ⁿ + k). В скобках стоит сумма нечетных чисел, значит она четна и потенциальное число делится на 2ⁿ⁺¹.

Ответ: Не лукавит.