2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача №5 Shortlist-a ММО 2004(Теория чисел)
Сообщение06.04.2007, 20:28 


28/12/05
160
Назовем натуральное число полосатым, если любые две соседние цифры в его десятичной записи имеют разную четность. Найдите все натуральные $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.

 Профиль  
                  
 
 
Сообщение06.04.2007, 20:54 


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

 Профиль  
                  
 
 
Сообщение06.04.2007, 21:13 


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

 Профиль  
                  
 
 
Сообщение06.04.2007, 21:28 


01/04/07
104
ФПФЭ
Да просто вспомнил о хорошем :roll: . А задача про полосатых разобрана во многих журналах.

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

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

 Профиль  
                  
 
 
Сообщение06.04.2007, 23:27 
Модератор
Аватара пользователя


11/01/06
5710
Для каждого натурального $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.$

 Профиль  
                  
 
 
Сообщение06.04.2007, 23:39 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение06.04.2007, 23:46 
Модератор
Аватара пользователя


11/01/06
5710
Да, что-то я упустил некоторые случаи.
Для $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.$

 Профиль  
                  
 
 
Сообщение06.04.2007, 23:54 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Нужен еще $2^k m$, $m$ не делится на 5.

 Профиль  
                  
 
 
Сообщение07.04.2007, 01:26 
Модератор
Аватара пользователя


11/01/06
5710
Для случаев $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}.$$

 Профиль  
                  
 
 
Сообщение08.04.2007, 06:14 
Модератор
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group