Число a будет делиться на число b состоящее только из едениц

[Hod]

Задача 34968, с сайта problems.ru https://problems.ru/view_problem_details_new.php?id=34968&x=0&y=0

Условие:
Докажите, что для любого числа $d$, не делящегося на $2 $ и на $5$, найдётся число, в десятичной записи которого содержатся одни единицы и которое делится на $d$.

Решение:
Рассмотрим числа, в десятичной записи которых содержатся одни единицы: $1, 11, 111, ...$ Поскольку таких чисел бесконечно много, то среди них найдутся два числа, имеющие одинаковый остаток при делении на $d$. Разность этих двух чисел будет иметь вид $A = 1...10...0$, то есть будет записываться несколькими единицами, за которыми следуют нули; кроме того, число $A $ делится на $d$. По условию $d $ взаимно просто с $10$, следовательно, число из одних единиц, полученное из $A $ вычеркиванием нулей, также делится на $d$.

Вопрос:
Не могу понять как доказать что мы покроем все возможные остатки от числа. Что я имею ввиду. Например возьмём число $d = 1989$ и нужно доказать что найдётся какое-то число из единиц, которое будет делиться на $d$. Т.е если предположить что такое возможно, то при деление в столбик мы когда-то должны будем получить $1790$. Далее мы снесём еденицу, и $17901 = 1989\cdot9$. Но мы же должны как-то дойти до этого остатка? Должны, поэтому возможен же вариант что мы не дойдём до него: это если дробь будет являться периодической. Т.е например может случиться такое, что в первый раз получили остаток от деления на $d $ остаток $173$, потом $259$, потом $163$, потом $3$, потом $6$, потом опять $163$. И как только мы попадаем на остаток от деления на котором уже были, мы зацикливаемся и далее остальные остатки не будут достигнуты \Rightarrow существует вероятность что необходимый остаток от деления не будет достигнут.

Предположения:
1. Либо можно доказать что дробь вида $m/n$, где $m $- число из единиц, а $n\not\vdots$10 не является периодической \Rightarrow мы сможем формировать бесконечную непериодическую дробь. \Rightarrow Мы когда-то достигнем необходимого остатка от деления
2. Либо даже если какие-то дроби вида $m/n$ являются периодическими, то тут 2 варианта: либо длина их периода $=$ кол-во возможных остатков числа $d$, Тогда мы пройдёмся по всем остаткам деления \Rightarrow необходимый остаток будет достигнут либо если длина их периода $<$ кол-во возможных остатков числа $d$, Тогда необходимый остаток от деления обязательно должен входить в список использованных.

[iifat]

Hod в сообщении #1515003 писал(а):

как доказать что мы покроем все возможные остатки от числа

А зачем нам все? Нам же надо два одинаковых.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»

[nnosipov]

Hod в сообщении #1515003 писал(а):

Не могу понять как доказать что мы покроем все возможные остатки от числа.

Это нельзя доказать, потому что это неверно. Возьмем, например, $d=11$. В этом случае число, записываемое одними единицами, может давать только два остатка: $0$ и $1$.

[TOTAL]

Hod в сообщении #1515003 писал(а):

Например возьмём число $d = 1989$ и нужно доказать что найдётся какое-то число из единиц, которое будет делиться на $d$. Т.е если предположить что такое возможно, то при деление в столбик мы когда-то должны будем получить $1790$.

Откуда следует, что должны получить $1790$?

[Dendr]

Hod в сообщении #1515003 писал(а):

Вопрос:
Не могу понять как доказать что мы покроем все возможные остатки от числа. Что я имею ввиду. Например возьмём число $d = 1989$ и нужно доказать что найдётся какое-то число из единиц, которое будет делиться на $d$.

Дирихле же. Всего может быть 1989 остатков, от 0 до 1988 включительно.
Берем 1988 произвольных (и попарно различных) натуральных чисел, и записываем в столбик.
Теперь в каждой строке выписывает число, состоящее из стольких единиц, сколько записано в начале строки.

Пробуем делить каждое из чисел на 1989. Если одно разделилось - ну, мы молодцы, угадали. Если нет - запишем в ту же строку остаток. Если остаток повторился - конструируем $A$ из ответа на problems.ru. Если ничего из этого не произошло, то значит все 1988 полученных остатков попарно различны, и не равны нулю.

Добавим еще одну строку с новым количеством единиц. Остаток для него неизбежно либо равен нулю, либо уже находится в третьем столбце.

Как уже сказано выше - нас не интересует, существует ли остаток, скажем, 574. Важно, что остатки с какого-то момента начинают повторяться. Не обязательно регулярно, но неизбежно.

P.S. Занятно, что из доказательства задачи напрямую следует, что если наименьшее делящееся на $d$ число состоит из $k$ единиц, то остатки от деления на $d$ чисел, записываемых меньшим, чем $k$, количеством единиц, непременно различны.

[ET]

TOTAL в сообщении #1515028 писал(а):

Hod в сообщении #1515003 писал(а):

Например возьмём число $d = 1989$ и нужно доказать что найдётся какое-то число из единиц, которое будет делиться на $d$. Т.е если предположить что такое возможно, то при деление в столбик мы когда-то должны будем получить $1790$.

Откуда следует, что должны получить $1790$?

Мне над этим тоже подумать пришлось, но следует
ТС пишет о делении в столбик и о том, что в конце мы должны выйти на без остатка
Последняя цифра при делении в столбик должна быть такая, чтоб 1989 умножить ан эту последнюю цифру стало заканчиваться на 1. Единственная такая цифра: 9
$9 \cdot 1989=17901$
Так что на предыдущем шаге деления в столбик должно быть 1790 (отбросим последнюю цифру)
А дальше, если я его правильно понял, ТС циклится на том, "что этого не может быть", или, точнее говоря, "может не быть", хотя доказательство того, что это быть надо сам же выше написал

[TOTAL]

ET в сообщении #1515051 писал(а):

TOTAL в сообщении #1515028 писал(а):

Hod в сообщении #1515003 писал(а):

Например возьмём число $d = 1989$ и нужно доказать что найдётся какое-то число из единиц, которое будет делиться на $d$. Т.е если предположить что такое возможно, то при деление в столбик мы когда-то должны будем получить $1790$.

Откуда следует, что должны получить $1790$?

Мне над этим тоже подумать пришлось, но следует

Если следует всего лишь из предположения, что найдётся какое-то число из единиц, которое будет делиться на $d$, то как-то не очень надежно следует.

Но если начать с того, что последовательность остатков зациклится (уж это-то точно!), то найдется число из единиц, которое будет делиться на $d$ (теперь это не предположение), поэтому при деление в столбик мы когда-то должны будем получить $1790$.

[ET]

TOTAL в сообщении #1515056 писал(а):

Если следует всего лишь из предположения, что найдётся какое-то число из единиц, которое будет делиться на $d$, то как-то не очень надежно следует.

Если $d=1989$ То следует надежно