Задача №5 Shortlist-a ММО 2004(Теория чисел)

[student]

Назовем натуральное число полосатым, если любые две соседние цифры в его десятичной записи имеют разную четность. Найдите все натуральные $n$, для каждого из которых существует полосатое число делящееся на $n$.

Английская версия:
We call a positive integer alternative if its decimal digits are alternatively odd and even. Find all positive integers $n$ such that $n$ has an alternative multiple.

[bobo]

Помню,в 10-м классе решил очень похожую задачу:
Назовем число n интересным, если найдется такое M, что сумма цифр числа M равна n, и само число M делится на n. Требовалось найти все интересные числа.

[student]

bobo Я тоже когда-то решил задачу про хорошие и плохие числа, а здесь требуется найти полосатых!

[bobo]

Да просто вспомнил о хорошем . А задача про полосатых разобрана во многих журналах.

Добавлено спустя 11 минут 55 секунд:

Тем более когда я общался со знакомым мне "международником"( он, как раз, в том году и писал олимпиаду), он сказал, что эти задачи ну ОЧЕНЬ похожи

[maxal]

Для каждого натурального $n,$ взаимно-простого с 10, существует кратное ему полосатое число. Например:

$$\frac{100^{\varphi(99n)}-1}{99},$$

где $\varphi(\cdot)$ - функция Эйлера.

Понятно, что если $n$ делится на $20,$ то кратного ему полосатого числа не существует (последние две цифры такого числа всегда четны). Осталось рассмотреть случаи делимости $n$ на $10$ и $50.$
Если $n=10\cdot m$ или $n=50\cdot m,$ где $(m,10)=1,$ то искомое полосатое число существует. Например:

$$50\frac{100^{\varphi(99m)}-1}{99}.$$

Таким образом, ответом будут все натуральные $n,$ некратные $20.$

[незваный гость]

«что-то, что-то не так, не так. // что-то не удалось.»
Например, $n = 4 k$ никогда не взаимно-просто с 10, но не всегда делится на 10. (Это пример, такие же «дыры» и дальше.)

Хотя с ответом я склонен соглашаться.

[maxal]

Да, что-то я упустил некоторые случаи.
Для $n=2m$ и $n=4m,$ где $(m,10)=1,$ работает:

$$12\frac{100^{\varphi(99m)}-1}{99}.$$

И остается еще рассмотреть случаи $n=5^k m$ и $n=2\cdot 5^k m,$ где $(m,10)=1.$

[незваный гость]

Нужен еще $2^k m$, $m$ не делится на 5.

[maxal]

Для случаев $n=5^k m$ и $n=2\cdot 5^k m,$ $(m,10)=1,$ решения можно построить индукцией по $k.$

Начнем с полосатого числа $5$ кратного $5.$
Пусть $t$ - полосатое число длины $k$ (возможно начинающееся с 0), кратное $5^{k}.$ Покажем как из него получить полосатое число длины $k+1$, кратное $5^{k+1}.$ Рассмотрим сравнение вида:
$t + 10^k s \equiv 0\pmod{5^{k+1}}$
или
$\frac{t}{5^k} + 2^k s \equiv 0\pmod{5}.$
Пусть $s_0$ - его минимальное решение (т.е. число от 0 до 4). Тогда в зависимости от первой цифры $t$, припишем спереди к $t$ цифру $s_0$ или $s_0+5,$ чтобы получить искомое число.

Пусть теперь $t$ - полосатое число длины $2k,$ делящееся на $5^{2k}.$ Можно считать, что $t$ - нечетное, а еще точнее оканчивающееся на 5.
Тогда $n=5^{2k}m$ и $n=2\cdot 5^{2k}m$ оба делят полосатое число

$$10 t\frac{10^{2k\varphi((10^{2k}-1)m)}-1}{10^{2k}-1}.$$

Добавлено спустя 21 минуту 5 секунд:

Случай $2^k m$ рассматривается почти аналогично:

Начнем с полосатого числа $32$ кратного $2\cdot 4.$
Пусть $t$ - полосатое число длины $2k,$ начинающееся с цифры 3 и кратное $2\cdot 4^k.$ Покажем как из него получить полосатое число длины $2(k+1)$, начинающееся с цифры 3 и кратное $2\cdot 4^{k+1}.$ Рассмотрим сравнение вида:
$t + 10^{2k} s \equiv 0\pmod{2\cdot 4^{k+1}}$
или
$\frac{t}{4^k} + 5^{2k} s \equiv 0\pmod{8}.$
Пусть $s_0$ - его минимальное решение (т.е. четное число от 0 до 6). Припишем к $t$ спереди двузначное число $32+s_0,$ чтобы получить искомое число.

Пусть теперь $t$ - полосатое число длины $2k,$ делящееся на $4^{2k}.$ Тогда $n=2^{2k}m$ делит полосатое число

$$t\frac{10^{2k\varphi((10^{2k}-1)m)}-1}{10^{2k}-1}.$$

[maxal]

Решение на AOPS:
http://www.artofproblemsolving.com/Foru ... hp?p=99760