Заметим, что если для исходного числа существует такой момент, то и для числа , полученного вычеркиванием всех девяток из исходного, он так же существует, поскольку каждое вычеркивание не меняет остаток при делении суммы цифр на 9.

Рассмотрим число . В силу неравенства , отношение количества восьмерок к оставшимся числам, больше 9. Отметим подряд идущие блоки по 9 чисел. Докажем, что существует блок, элементами которого являются лишь восьмерки. Пусть это не так, тогда в каждом блоке есть цифра отличная от восьмерки, следовательно, количество цифр, не являющихся восьмерками, хотя бы от общего количество, что противоречит полученному неравенству.

Рассмотрим блок, состоящий только из восьмерок. Пусть число, полученное из вычеркиванием всех цифр до найденного блока, имеет остаток при делении на 9. Каждое вычеркивание 8 увеличивает остаток при делении на 9 на 1, следовательно, вычеркнув элементов в блоке, мы получим искомое число.

Воспользуемся алгоритмом Евклида для получим

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

Аналогично получаем, что

А также

Складывая эти три неравенства, получаем

В качестве примера на можно предъявить, например, В этом случае

Предположим, что Семёнов сказал правду, то есть в первый раз числитель и знаменатель имеют общий делитель больше единицы через минут.

Получится , откуда делится на какое-то число из множества давайте это число обозначим буквой

Заметим, что делится на (если непонятно, то посмотрите, что такое ). Тогда тоже делится на .

Но отсюда сразу следует, что дробь уже через шагов сократима: . А Семёнов сказал, что первый раз дробь сократима будет через шагов. Но . Семёнов, ты не прав!

Имеет место один из двух случаев.
(a) Пусть оба наименьших делителя и — простые числа. Тогда простым будет число откуда Поскольку числа и взаимно просты, то откуда и Но тогда в силу выбора получаем и
(b) Пусть наименьшие делители имеют вид и где простое. Тогда простым будет число откуда Поскольку числа и взаимно просты, то Это возможно только в случае В этом случае откуда Но этот случай невозможен, так как у один из двух наименьших делителей это

Предположим, что число подходящее. Пусть где нечётное. Если то условие говорит, что делится на что возможно только при условии Если и где минимальный простой нечетный делитель то делится на откуда имеем значит, Число или имеет остаток по модулю или имеет остаток по модулю Тем самым число является подходящим, если число может иметь остаток по модулю Это значит, что в каждом ряду из последовательных четных чисел ровно пять подходящих. Используя равенство получаем ответ

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

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

С другой стороны, . Отсюда следует, что . Пусть . Тогда одно из , скажем, равно 1 , а тогда (простота числа 5). В случае, когда , получаем уравнение , то есть . Итак, все числа , удовлетворяющие условию задачи, имеют разложение на простые множители вида либо , либо . Перечислим те из них, которые лежат между 400 и 600.

Числа . Имеем , тем самым, . Итак, . Следовательно, , а, значит,

Выписывая всевозможные произведения , лежащие в промежутке от 400 до 600 , с вышеуказанными и , получаем .

Единственное , лежащее между 400 и 600 , есть . Итого получаем список всех возможных чисел :

Запишем равенство в следующем виде: Если мы докажем, что НОД и равен то тогда будет кубом. Предположим, что в этой ситуации не является кубом. Тогда в разложение входит какое-то простое число в степени, не кратной Скобка на не делится, значит входит в в степени, не кратной чего быть не может.

Итак, докажем взаимною простоту и Ясно, что НОД этих чисел равен НОДу и предположим, что этот НОД равен Тогда делится на Пусть делится на некоторое простое число тогда на делится и Значит, также делится на Также делится на а значит и на Получается, что НОД и больше противоречие. Значит, НОД и равен что и требовалось.

Ясно, что подходит, ведь произведение из условия будет равно Рассмотрим теперь Обозначим произведение его делителей буквой

Если число не является точным квадратом, то его делители можно разбить на пар с произведением в каждой (если число делится нацело на , то оно делится нацело и на ). Например, . Так что делители бьются на пары с произведением в каждой, откуда

По условию , тогда Число должно иметь делителей.

Если число является точным квадратом, то есть ещё делитель поэтому — противоречие с тем, что — целое число пар.

Для количество различных делителей равно (берём каждое простое в каждой степени, считая нулевую). Если число должно иметь ровно делителей, то .

При получаем . Среди чисел от до подходит только

При получаем Из условия на промежуток

.

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

Решим уравнение в натуральных числах. Преобразуем левую часть следующим образом: Теперь запишем уравнение в виде Домножим равенство на и разложим левую часть на множители через разность квадратов: Осталось перебрать возможные варианты. Для упрощения перебора заметим, что Следовательно, для скобочек возможны следующие варианты: и и и и Осталось разобрать каждый случай и написать ответ.

Заметим, что отсюда и Пусть содержит некоторый делитель который взаимно прост с и — тогда на это число должны делиться и что невозможно, поскольку Отсюда делится только на (из простых чисел). Если какое-то простое число входит в него большей степени то делит и значит, степень каждого простого не больше первой. То есть может принимать значения Первые три невозможны, пятёрка даёт нам что подходит. Пятый случай также невозможен, в шестом условие взаимной простоты не выполнено. Для есть случаи и нам подойдёт только второй. Для получаем — подойдут первый и третий случаи. Остаётся выписать ответ.