Конкурсная задача ММ155 (4 балла)
Существует ли цепочка из 1000 последовательных натуральных чисел, каждое из которых имеет не менее 1000 натуральных делителей?
Решение
Приведу решение Алексея Волошина:
Возьмём 1000000 различных простых чисел p1, p2,…, p1000000, больших 1000. По китайской теореме об остатках найдётся такое n, которое при делении на pi дает остаток pii- [(i-1)/1000]. Тогда n делится на p1, p2,…, p1000, n+1 делится на p1001{1001}, p1002,…, p2000 и т.д.
Обсуждение
Предлагая задачу ММ155, я имел в виду решение наподобие приведенного. К моему удивлению в четырех из семи поступивших решений не используется (по крайней мере, в явном виде) китайская теорема об остатках.
Сразу же после публикации задач 16-го тура, один из авторитетных «подпольных марафонцев» (тех людей, которые следят за Марафоном, но не присылают решений) покритиковал меня за тривиальность задачи ММ155 и избитость идеи, лежащей в ее основе. Его слова оказались пророческими: http://dxdy.ru/topic53659.html?sid=eb40b985201f7436aa989c3b802ac969.
Тот же «зритель» Марафона познакомил меня с задачкой, в которой идея ММ155 оформлена более изящно: Целая точка на плоскости (или в пространстве), отличная от начала координат, называется невидимой, если её координаты не взаимно просты. Нужно доказать, что существуют сколь угодно большие квадраты, все целые точки в которых невидимы.
Награды
За правильное решение задачи ММ155 Виктор Филимоненков, Олег Полубасов, Сергей Половинкин, Дмитрий Пашуткин, Алексей Волошин и Николай Дерюгин и Анатолий Казмерчук получают по 4 призовых балла.
Эстетическая оценка - 4.4 балла
Разбор задачи ММ155 подготовил Владимир Лецко