Число с суммой цифр n делящееся на n

[NiGHTeR]

Помогите решить,

Надо доказать что для любого n найдется число с суммой цифр n которое делится на n

я так думаю, что число чисел, делящихся на n длины меньше $k$ есть $[10^k/n]$ , а число чисел с суммой цифр n длины меньше k есть $C_{n-1}^{k-1}$ отсюда для выполнения условия задачи достаточно чтобы для некоторого k выполнилось:
$10^k(1-1/n)<C_{n-1}^{k-1}$ т.е. число чисел с суммой цифр n было больше чем число чисел, не делящихся на n.

[gris]

Вряд ли это выполняется. Хотя бы на примере девятки. Количество чисел в любом диапазоне не делящихся на 9 приближённо в 8 раз больше чисел, сумма цифр которых равна 9.

[NiGHTeR]

а в каком направлении тогда хотя бы думать?

[AKM]

NiGHTeR,

заголовочек поадекватней поставьте, плииз, пока кнопка Правка активна.

[gris]

Может быть попробовать как то построить число? Добавление нулей, например, не меняет сумму цифр.

[NiGHTeR]

да, но прибавление нулей никак не меняет и делимости на какое либо число

[gris]

Нули можно прибавлять и в середину.
Я бы попробовал построить такие числа. Для первого десятка всё тривиально. А вот для 11... Сумма всех цифр 11, а сумма цифр, стоящих на чётных позициях, должна быть равна сумме цифр на нечётных позициях или отличаться от неё на 11. Вот тут нули-то и пригодятся. Минимильное число 2090.
Ещё 1010101010101010101010
Для 12 — 48.
13 — 247
Ну вот пока больше идей нет

Нужно какое-то специальное построение.

Или попробовать поанализировать числа, кратные $n$. Сумма цифр ассциируется с остатком от деления на 9.

[NiGHTeR]

ну в общем случае что то я не представляю как построить(

[ИСН]

там сложно. общий случай распадается на два: взаимно простых и нет.
Докажите для начала, что есть число из одних девяток, делящееся на 2011.

[NiGHTeR]

ну $10^{2010}-1$ делится на 2011

[ИСН]

О, здорово. Как доказывается, знаете?
Теперь точно так же докажите, что найдётся число вида 100...001, тоже делящееся на 2011.
И число вида 100...0000057483205674321 (цифры после нулей - от балды).
И вообще любое число, если в него напихать достаточно нулей.

[NiGHTeR]

ну да, то что $(x^p-1)=0(\mod p)$ при простом p

можно рассмотреть мультипликативную группу по модулю n
в ней $\varphi(n)+1$ элементов,
и если $(n,10)=1$ то 10 входит в эту группу, тогда если $(\varphi(n),n)=1$ то порядок 10 в этой группе ровно $\varphi(n)+1$ и тогда перебирая всевозможные степени 10 мы получаем различные остатки по модулю n?

-- Чт июн 09, 2011 01:07:23 --

условие $(\varphi(n),n)=1$не нужно

-- Чт июн 09, 2011 01:37:44 --

спасибо всем, решил)

[VAL]

gris в сообщении #455887 писал(а):

. А вот для 11... Сумма всех цифр 11, а сумма цифр, стоящих на чётных позициях, должна быть равна сумме цифр на нечётных позициях или отличаться от неё на 11. Вот тут нули-то и пригодятся. Минимильное число 2090.

А чем Вам 209 не угодило?

[gris]

VAL, а я... ах, да! Я же написал: "минимильное число". Это как бы минимальное, но большее тысячи. А Ваше число, к сожалению, не минимильно.

upd: убрал смайлик. Не было спички юмора.

[VAL]

NiGHTeR в сообщении #455925 писал(а):

ну да, то что $(x^p-1)=0(\mod p)$ при простом p

Только, все же, $x^{p-1}$.

-- 09 июн 2011, 07:43 --

gris в сообщении #455951 писал(а):

VAL, а я... ах, да! Я же написал: "минимильное число". Это как бы минимальное, но большее тысячи. А Ваше число, к сожалению, не минимильно

Смайлик вижу. Но юмора, виноват, не понял