Докажем, что существует число Q, что в десятичной записи числа Q*2^2015 нет ни одного нуля. (запись 2^2015 означает 2 в степени 2015).
<hr />
Запишем приведенное выражение, как Qn*2^n = Nn, где Qn и Nn - натуральные числа.
Докажем утверждение, что всегда найдется число из n цифр Nn, в записи которого встречаются только единицы и двойки, которое делится на 2^n.
Доказательство проведем по индукции.
- n = 1. N1 = 2 - делится на 2^1 = 2.
- Пусть мы построили число Nn = Qn*2^n. То есть Nn делится на 2^n. Припишем к этому числу Nn слева 1 или 2. Рассмотрим оба получившихся числа:
10^n + Nn = 10^n + Qn*2^n = 2^n*(5^n + Qn)
2*10^n + Nn = 2*10^n + Qn*2^n = 2^n*(2*5^n + Qn)
[Тут мы воспользовались тождеством: 10^n = 5^n*2^n]
Одно из этих чисел делится на 2^(n + 1) = 2^n*2, поскольку одно из чисел (5^n + Qn) и (2*5^n + Qn) чётно. Так как 5^n - нечетно, а 2*5^n - четно и Qn - не известно.
Утверждение доказано.
<hr />
Теперь сам алгоритм нахождения такого числа.
1 - 2
2 - 12 (приписываем слева 1 или 2, чтобы делилось без остатка на 2^2 = 4, тут подходит 1)
3 - 112
4 - 2112
5 - 22112
.
10 - 1212122112
.
и так далее до 2015. В итоге получится число из 2015 цифр, в записи которого встречаются только 1 или 2 (нет ни одного нуля). Оно будет делиться на 2^2015.