Математическая задача

stat7221748

Выписаны в ряд числа от 123456789101112 и т д . Доказать, что какое нибудь из образованных таким образом чисел будет делиться на 2003.
А мыслей чего то нету

iri3955

Выберем a:
10^a = -1 (mod 2003)
тогда дойдём до а-значных чисел, будет происходить следующее:
Добваление часла k - то же, что и умножение на 10^a и плюс k.
По модулю 2003 это сравнимо с умножением на -1 и прибавлением k.
Таким образом если сумма была s, то
Дальнейшие числа будут сравнимы с s, -s + k, s - k + (k + 1) = s + 1, -s - 1 + (k + 2 s + 1 - (k + 2) + (k + 3) = s + 2.
Каждай чётный член на 1 больше предыдущего (чётного) по модулую 2003.
если 10^a > 2*2003, то мы победили, а оно больше.
Существует ли такое a, я, к сожалению, не знаю Были теоремы какие-то, но я их в упор не помню.
По идее a должно делиться на 1001...

Sanych

Такое a существует в том и только в том случае, если 10 не является квадратом по модулю 2003.
И на самом деле, его не существует.

iri3955

Эххх

margo11

А может забить на -1? Почему бы не взять а такое, что 10^a = 1 (2003)?

iri3955

и чё будет?
будет s + n(n+1)/2 - тока половина остатков

a101

Если совсем грустно, то можно попробовать посчитать остаток, если выписаны числа до, например, 515. Будет немного муторно, но на 2003 поделится.

boyeva

что-то похожее решалось "принципом Дирихле". типа в 2004 чисел обязательно повторится остаток. там нужно было вычесть оно из другого. может и здесь как-то так же можно

COR72Z

пальцем в небо

a101

Давайте возьмем любую степень 10-ки, например 2003. Пусть x = 10^2003 (=10 mod 2003). Расмотрим как ведет себя последовательность в том районе (2003 значных чисел).

s -> s*x + n

Сделаем эту операцию 2002 раза. Получим

s -> s * (x^2002) + N(x^2001 + x^2000 + ... + x^0) + k

где N - число с которого начали добавлять.

x^2002 = 1 mod 2003
x^2001 + x^2000 + ... + x^0 = (x^2002 - 1) / (x - 1) = 0 mod 2003

То есть за такую операцию у нас остаток от деления на 2003 изменится ровно на k. Осталось проверить (или подобрать такую степень чтобы k != 0 mod 2003.

Что такое k?
k = x^2001 * 0 + x^2000 * 1 + x^1999 * 2 + ... x^0 * 2001

a101

продолжение ...

k = x^2001 * 0 + x^2000 * 1 + x^1999 * 2 + ... x^0 * 2001 = 2001 * (x^2001 + x^2000 + ... + 1) - x^2001 * 2001 + x^2000 * 2000 + .. x^0 * 0 = (первая часть = 0) 0 + x*(2001 * x^2002 - 2002 * x^2001 + 1) / (x-1)^2

То есть надо проверить, что
2001 * x^2002 - 2002 * x^2001 + 1 != 0
умножим все на x
2001 * x^2003 - 2002 * x^2002 + x = 2001 * x - 2002 + x = 2002(x-1) != 0

Все ок.

fift

при делении остатки то не учел!

a101

Какая разница? Если перед делением остаток не был равен 0, то и после не будет. Нам же не нужно точно его посчитать, просто показать, что он не 0, так как 2003 простое.

fift

так как 2003 простое
ошибка! хотя может и нет...

a101

Собственно у меня все решение завязано на то, что 2003 - простое. Последние деления - это малая часть.

fift

зато твое доказательство не проходит для 2004

a101

Это я знаю. Но, как понимаю, задача ровно завязана на простоте была.
Как доказывать, что там будет делиться на любое число - я не знаю. Да и не очевидно мне это.

fift

Я кажется знаю наметки как доказать для 10

a101

Кстати, если я правильно понимаю, то если N не делится на 2, 3, 5 (то есть взаимопросто с 10 и (10 - 1 то видимо мое решение проходит, если вместо 2002 писать fi(N) - число взаимопростых с N. Кроме этого требуется, чтобы (N, fi(N = 1.

fift

если N не делится на 2, 3, 5
ошибка! 10 делится на 2 и на 5

a101

Я не основание имел ввиду, а на что деление нужно.

fift

Я не основание имел ввиду, а на что деление нужно.
тогда я вообще ничего не понял

a101

Что есть числа делящиеся не только на 2003 (или другое простое а и на числа N, для которых выполняется несколько условий написанных выше.

Основание счисления (что пишем в 10-й системе) я не трогаю.

stat7221748

Спасибо, только ничего не понятно если честно. Кстати, эта задачка предлагалась на олимпиаде для 10-11 классов.

seregaohota

Решили уже? 2003 простое число. Я не решал и топик путью не читал. Составил прогу, выдаёт минимальные решения при
515, 2273, 2440, 4134, 6054, 9880, 11643, 16770, 18550,...
если чем поможет.

Galina76

Я кажется знаю наметки как доказать для 10
в смысле 10 вместо 2003?
тогда можно перебором последовательным, довольно быстро получится

fift

тогда можно перебором последовательным, довольно быстро получится
хм, ну-ну

1853515

в смысле 10 вместо 2003?

если должно делиться на 10, то, очевидно, число 12345678910 делиться на 10
или я что-то не так понял?

fift

Я утверждаю, что любое число, оканчивающееся на ноль ОБЯЗАНО делится на 10.
Оставить комментарий
Имя или ник:
Комментарий: