|
|
 |
Условие
Для любого натурального числа n существует составленное из цифр 1 и 2 число, делящееся на 2n. Докажите это.
(Например, на 2 делится 2, на 4 делится 12, на 8 делится 112, на 16 делится 2112...)
Решение 1
Докажем, что разные n-значные числа, составленные из цифр 1 и 2, дают разные остатки при делении на 2n.
Действительно, разность d таких чисел можно представить в виде an·10n–1 + an–1·10n–2 + ... + a2·10 + a1, где каждое из чисел ai равно 0 или ±1. Рассмотрим наименьший номер k, для которого ak ≠ 0. Очевидно, что d делится на 2k–1, но не делится на 2k. Таким образом, d делится на 2n только тогда, когда d = 0.
Но и таких n-значных чисел, и различных остатков ровно 2n, поэтому одно из этих чисел дает остаток нуль, то есть делится на 2n.
Решение 2
Докажем по индукции более сильное утверждение:
для любого натурального n существует составленное из цифр 1 и 2 n-значное число, кратное 2n.
База: 2 делится на 2.
Шаг индукции. Пусть n-значное число A из единиц и двоек делится на 2n. Число 10n делится на 2n, но не делится на 2n+1. Следовательно, ровно одно из чисел 10n + A, 2·10n + A кратно 2n+1.
