Раз-два, раз-два

Можно заметить, что для любого натурального N существует число, состоящее из N цифр 1 или 2, которое делится на 2^N. Причем, если такое K-значное число делится на 2^K, то разместив перед ним 1 или 2 всегда можно получить (K+1)-значное число, делящееся на 2^K+1. Откуда очевидным образом вытекает алгоритм поиска нужного числа (динамическое решение): при K=1 мы имеем число 2, далее при увеличении значения K мы будем к предыдущему числу приписывать 1 слева и проверять его делимость на 2^K, при положительном исходе будем оставлять 1, иначе заменять ее на 2. Ограничения в задаче позволяют осуществлять проверку делимости числа на 2^K с использованием K делений на 2 длинного числа (длинная арифметика).

При прочтении данного решения могут возникать вопросы: как возможно прийти к данному решению и почему утверждение о построении такой последовательности является верным? Обычно, при решении подобных задач полезно попытаться найти какую-либо закономерность, выписав первые элементы искомой последовательности. Для N, меньших 20 это можно сделать "в лоб", простым перебором с проверкой (ведь понадобится перебрать не более 2²⁰ чисел). В результате получаемая последовательность (2, 12, 112, 2112, 22112, 122112, 2122112, 12122112, 212122112, ...) приводит к вышеописанной идее.

Используя метод математической индукции, возможно доказать справедливость данного алгоритма решения. Покажем, что для любого натурального N существует число, состоящее из N цифр 1 или 2, которое делится на 2^N. Для N=1 решение очевидно, это число 2. Теперь предположим, что для некоторого натурального K данное условие так же выполняется, а это значит, что существует некоторое число X, которое делится на 2^K и состоит ровно из K цифр. Нам нужно показать, что всегда возможно приписав слева к числу X цифру 1 или 2, получить число, делящееся на 2^K+1 (заметим, что тогда число будет состоять ровно из K+1 цифры). Число X либо делится на число 2^K+1, либо не делится. Если деление имеет место быть, то к числу X нужно дописать слева цифру 2 и тогда оно так же будет делиться на 2^K+1. Действительно, ведь в результате дописывания двойки мы получим число 2*10^K + X, где оба слагаемых делятся на 2^K+1 (первое делится потому, что оно равно 2^K+1*5^K, а второе - по предположению), а значит и само число тоже делится. В случае, когда X не делится на 2^K+1, необходимо приписать к X слева цифру 1, что приведет к делимости полученного числа на 2^K+1. Действительно, полученное число тогда будет равно 10^K + X = 2^K(5^K+Y), здесь X = 2^K*Y. В скобках мы имеем сумму нечетных чисел, результатом которой обязательным образом будет четное число, что при умножении на 2^K даст число, делящееся на 2^K+1, что и требовалось доказать.

[Все попытки] [Задача]