Шестизначное число

[Murzilka]

Существует ли такое шестизначное (в десятичной записи) натуральное число $n$, что среди чисел вида $mn$, где $1\le m\in\mathbb N\le500000$, нет ни одного числа, оканчивающегося (также в десятичной записи) шестью одинаковыми цифрами?

[Руст]

Ясно, что $(n,10)=1$, иначе найдется такое m, что mn заканчивается шестью нулями.
Соответственно для любого $a$ разрешимо сравнение $xn=a \mod 10^6$ c $x<10^6$ .
Пусть $x_1$ решение для $a=111111.$. Возьмем $a=c*111111, c<10$. Тогда решением для такого $a$ будет $cx_1\mod 10^6$. Можно выбрать $x_1$ так, чтобы все они были больше $500000$ и даже больше $999990$, например взяв $n$, так, чтобы было $x_1=999999$, т.е. $n=9^{-1} \mod 10^6 =\frac{8000001}{9}=888889.$

[Murzilka]

Руст в сообщении #469821 писал(а):

Ясно, что $(n,10)=1$, иначе найдется такое m, что mn заканчивается шестью нулями.
Соответственно для любого $a$ разрешимо сравнение $xn=a \mod 10^6$ c $x<10^6$ .
Пусть $x_1$ решение для $a=111111.$. Возьмем $a=c*111111, c<10$. Тогда решением для такого $a$ будет $cx_1\mod 10^6$. Можно выбрать $x_1$ так, чтобы все они были больше $500000$ и даже больше $999990$, например взяв $n$, так, чтобы было $x_1=999999$, т.е. $n=9^{-1} \mod 10^6 =\frac{8000001}{9}=888889.$

А почему число 999997 не годится?

[Руст]

Годится. Я привел максимальное по $N$ решение. Если $n=888889$, то при любом $1\le m\le N=999990$ число $mn$ не оканчивается на шесть одинаковых цифр.

[Murzilka]

Руст в сообщении #469833 писал(а):

Годится. Я привел максимальное по $N$ решение. Если $n=888889$, то при любом $1\le m\le N=999990$ число $mn$ не оканчивается на шесть одинаковых цифр.

Но если 999997 годится, то Ваше решение слишком сложное для такой задачи, а сама задача теряет олимпиадный характер, ведь можно просто начать перебирать "с конца" - числа 999999 и 999998 очевидно не подходят, а 999997 - да.
Вы согласны со мной?

[Руст]

Согласен только в том, что в условии надо было менять $N$ большим числом, не меньше 900 000. Или спрашивать, сколько таких $n$ имеется для $N=500 000$.

[Murzilka]

Руст в сообщении #469843 писал(а):

Согласен только в том, что в условии надо было менять $N$ большим числом, не меньше 900 000. Или спрашивать, сколько таких $n$ имеется для $N=500 000$.

Ну вот, а теперь загляните вот сюда:

http://problems.ru/view_problem_details ... p?id=98321

Задаче зачем-то присвоили аж пятую (!!!) сложность. На мой взгляд, в том виде, в котором она есть, она и на нулевую-то не очень тянет.

А вот те два варианта усложнения, что Вы предложили, предлагаю рассмотреть.

[Руст]

По сути они решили в точности как я и нашли значение $n$ максимизирующее $N$.