|
|
 |
Условие
Доказать, что если натуральное число k делится на 10101010101, то в его десятичной записи по крайней мере шесть цифр отличны от нуля.
Решение
Если число A, делящееся на 10101010101, имеет не более 12 цифр, то оно имеет вид abababababab, и задача решена. Остаётся свести задачу к этому случаю.
Число 10101010101 обозначим через M.
Лемма. Если A делится на M и имеет больше 12 цифр (считая нули), то найдётся число B, также кратное M, меньшее A и имеющее не больше ненулевых цифр, чем A.
Доказательство. Пусть A = a1a2...an. Вычеркнем его первую цифру a1 и прибавим её же на 12 разрядов ниже. Полученное число будет меньше исходного: легко проверить, что мы просто вычли из числа A число
a1(10n–1 − 10n–13). В скобках стоит произведение 10n–13(1012 − 1); второй сомножитель делится на M (это число из 12 девяток), так что разность делится на M. Остаётся заметить, что в получившемся числе значащих (не нулевых) цифр не больше, чем в исходном.
Теперь, если A делится на M, вычтем из A его первую цифру, умноженную на 10n–13(1012 − 1). С полученным числом проделаем ту же операцию и будем поступать так до тех пор, пока не доберёмся до 12-значного числа. Так как в нём не меньше шести значащих цифр, то и в A не меньше шести значащих цифр.
