Разминка

Конкурсная задача ММ181 (3 балла)

Существует ли натуральное число n, среди остатков от деления которого на все натуральные числа меньшие n чаще всего встречается остаток 2013?

Решение

Привожу решения Андрея Халявина и Олега Полубасова.

Обсуждение

Числа n с рекордным (бОльшим, чем у всех меньших чисел) значением τ(n) называются highly composite numbers (вслед за Андреем Халявиным я буду называть их «граничными»). Эти числа упомянуты как в строгих, так и в приблизительных обоснованиях обобщения ММ181. Они, конечно же, есть в OEIS (A002182). Числа, которые Андрей Халявин в своем решении обозначил через G_n, также есть в OEIS (A086332). Правда, их было приведено всего 16 штук. При подготовке данного разбора я добавил в OEIS список, содержащий первые 38 чисел G_n. Утверждение Андрея о том, числа G_n не обязаны существовать для всех n, скорее всего, является перестраховочным. Исследование первой тысячи граничных чисел показывает, что G_n встречаются среди них относительно редко. В среднем на каждые 27 граничных чисел встречается одно G_n и интервал между G_n имеет тенденцию к возрастанию.

А вот последовательности A230399 в OEIS не было. Но в связи с обобщением ММ181 она появилась.

Как водится я испытывал трудности при присуждении призовых баллов. Ясно, что те конкурсанты, которые только нашли подходящие числа, но не сделали попыток обобщения, получили номинал. Столько же баллов получили те, кто обобщил задачу, даже привел (не слишком строгие) обоснования бесконечности требуемых чисел для любого данного остатка, но при этом не нашел ни одного подходящего числа даже для 2013 На один балл выше номинала оценено решение, где найдены подходящие числа и сделаны (но не отягощены доказательствами) обобщения. Наиболее сложной для меня задачей было оценить решения Олега и Андрея. С одной стороны, у Андрея охвачен более общий случай, а у Олега доказана только бесконечность множества чисел, для которых именно 2013 является наиболее часто повторяющимся остатком. Но: Во-первых, решение Олега легко обобщается с k = 2013 на любое k. А во-вторых, решение Андрея представляется мне неоправданно тяжеловесным (возможно это следствие того, что сам аккуратного доказательства не делал). Учитывая вышесказанное, я несколько раз менял призовые баллы Андрея и Олега. Текущая версия представлена в разделе «награды»

Приведу набросок своего доказательства общего утверждения: для любого целого неотрицательного k найдется бесконечно много натуральных чисел n, при делении которых на все натуральные числа, меньшие n, остаток k встречается наиболее часто. Почему только набросок? Жаждущие деталей могут заглянуть в решение Олега (в идейном плане оно близко моему), а особо жаждущие могут попытаться осилить решение Андрея (оно тоже основано на тех же идеях) Мой же опус предназначен для тех, кому лень углубляться в детали, но хочется понять суть.

Не теряя общности, можно считать, что k достаточно велико. Например, больше 100. Возьмем большое граничное число b, например, имеющее не менее k различных простых сомножителей. Ясно, что в каноническом разложении b встречаются все первые k простых чисел, причем показатели идут в порядке невозрастания. Пусть c - ближайшее к b (неважно с какой стороны) число, имеющее не менее чем τ(b)-k делителей. Тогда несколько первых простых делителей b, произведение которых больше k, обязаны входить и в разложение c. (Если это не так, заменим в c какие-то из больших делителей на отсутствующие и, увеличив показатели степени у маленьких делителей, получим число меньшее b, но имеющее больше делителей, что противоречит выбору b.) Но тогда НОД b и c больше k, то есть c отстоит от b более чем на k и, значит b+k - искомое число.

Замечу, что на практике не обязательно стартовать исключительно с граничных чисел. В качестве b, как правило, годятся любые большие числа, насыщенные мелкими делителями.

В заключение сформулирую еще один вопрос (ответ на который, я лично искать не собираюсь У числа 525 нет одного явного лидера среди остатков от деления на числа от 1 до 525 (я чуть-чуть изменил исходное условие, но это не важно). Каждое из чисел 0, 5, 21 встречается среди остатков по 12 раз. Возникает вопрос: для любого ли конечного множества остатков найдется число, для которого данные остатки будут встречаться чаще других и одинаковое число раз? Такая вот «Монгольская теорема об остатках»

Награды

За решение и обобщение ММ181 Андрей Халявин получает 8 призовых баллов, Олег Полубасов - 7 призовых баллов, Сергей Половинкин - 4 призовых балла, а Виктор Филимоненков, Антон Никонов, Алексей Волошин, Николай Дерюгин, Евгений Гужавин и Дмитрий Пашуткин - по 3 призовых балла.

Эстетическая оценка задачи 4.1 балла

---