Интересное свойство числа 19

[DrVirogov]

Когда знаешь решение, трудно понять, насколько оно трудное или простое.
Собственно, в этом и вопрос - помогите оценить вот эту задачу (например, годится ли она для студенческой олимпиады).

Берем число, которое делится на 19 и записываем его в двоичной системе, например

$19 \cdot3 = 57 = (111001)_2$

Переворачиваем двоичную запись и рассматриваем ее как десятичное число.
Это число будет делиться на 19, что и нужно доказать.

$100111 = 19 \cdot5269$

[Ktina]

Это не верно!
Возьмите само число 19.
В двоичной оно будет 10011.
Перевернём: 11001.
А это уже 25

-- 31.12.2012, 02:18 --

А нет, пардон, не так поняла условие задачи.

[nnosipov]

Фокус основан на том, что $10^{-1} \equiv 2 \pmod{19}$. При составлении варианта задач для любой олимпиады всегда нужны задачи самого разного качества --- как сложные, так и довольно простые. Эта задача относится, очевидно, к категории последних, если иметь в виду именно студенческую олимпиаду. Но это не означает, что почти все участники обычной среднестатистической олимпиады её решат. В общем, вполне можно предлагать.

[Shadow]

Напишу свое решение, наверное можно и проще.

$\\A=a_0+2^1a_1+2^2a_2+\cdots 2^na_n\\ B=10^na_0+10^{n-1}a_1+10^{n-2}a_2+\cdots a_n$

Рассмотрим число $C=10^nA-B=\sum\limits_{k=0}^n \Left(10^n\cdot 2^k-10^{n-k}\Right)a_k$

Все коэффициенты в сумме делятся на 19

$10^n\cdot 2^k-10^{n-k}=10^{n-k}\Left(10^k\cdot 2^k-1\Right)$

$20^k \equiv 1 \pmod{19}$

C делится на 19, A делится по условие, а значит и B.

[DrVirogov]

С наступающим новым годом!
Спасибо за ответы. Пожалуй, лучше считать это фокусом, а не задачей. Можно было бы сформулировать проблему в общем виде, с системами счисления по основаниям M и N и делимостью на MN-1, но тогда решение становится слишком очевидным и пропадает эффект неожиданности.