Задача 3. Саша стирает делители

Делители разбиваются на пары

Если $d$ — делитель $N$, то и $\frac{N}{d}$ — делитель, ведь $N = d\cdot\frac{N}{d}$. Назовём два таких делителя парой: их произведение равно $N$.

Например, у числа $60$ двенадцать делителей

и пары такие:

Посмотри, где стоят пары: самый маленький делитель — в паре с самым большим, второй — с предпоследним и так далее. Так бывает всегда. Каждый делитель $e$ попадает в пары ровно один раз — как пара делителя $\frac{N}{e}$. А чем больше делитель $d$, тем меньше его пара $\frac{N}{d}$. Поэтому, если пройти по делителям от меньшего к большему, их пары пройдут все те же делители, но от большего к меньшему. Значит, $k$-й делитель с начала стоит в паре с $k$-м делителем с конца.

Если $N$ — квадрат числа, например $36 = 6\cdot 6$, то средний делитель $6$ — в паре сам с собой.

Саша стирает целые пары

Сто наименьших делителей — это первые сто, а их пары — как раз сто наибольших. Значит, Саша стёр ровно сто пар целиком, и оставшиеся делители тоже складываются в целые пары (и, может быть, средний делитель, если $N$ — квадрат).

Стереть по двести — значит стереть эти же сто пар и ещё сто пар, которые идут за ними. Поэтому после стирания по двести остаётся часть тех же пар, что оставались после стирания по сто.

Условие «больше $400$ делителей» нужно как раз для того, чтобы по двести с каждого края стереть было можно и что-то осталось.

Число N чётное, пар из двух нечётных нет

Если бы $N$ было нечётным, все его делители тоже были бы нечётными: у нечётного числа чётных делителей нет. Тогда после стирания осталось бы больше $400 - 200 = 200$ нечётных делителей и ни одного чётного — не поровну. Значит, $N$ чётное.

Произведение двух нечётных чисел нечётно, а произведение чисел пары равно чётному $N$. Поэтому пары из двух нечётных делителей нет. Остаются пары двух видов:

• «чётное и нечётное» — например, $3$ и $20$ у числа $60$;

• «два чётных» — например, $6$ и $10$.

А средний делитель, если $N$ — квадрат, чётный: квадрат нечётного числа был бы нечётным.

Что значит «поровну»

Пусть после стирания по сто осталось $x$ пар «чётное и нечётное» и $y$ пар «два чётных», а может быть, ещё и средний делитель. Нечётные делители есть только в смешанных парах, по одному в каждой, поэтому нечётных осталось $x$. Чётных — по одному в каждой смешанной паре и по два в каждой паре «два чётных», то есть $x + 2y$, и ещё один, если остался средний делитель.

Чётных и нечётных поровну, значит, лишних чётных нет: $y = 0$ и среднего делителя нет. Итак, после стирания по сто остались только пары «чётное и нечётное».

Например, у $60$ после стирания по два остаются пары $3$ и $20$, $4$ и $15$, $5$ и $12$, $6$ и $10$. Из-за пары $6$ и $10$ чётных пять, а нечётных три. А у $90$ после стирания по два остаются пары $3$ и $30$, $5$ и $18$, $6$ и $15$, $9$ и $10$ — все смешанные, и чётных и нечётных по четыре.

Стираем по двести

Если бы Саша стёр по двести, осталась бы часть тех пар, что остались после стирания по сто (шаг 2). Все те пары — «чётное и нечётное» (шаг 4). Каждая такая пара даёт один чётный и один нечётный делитель, поэтому и после стирания по двести чётных и нечётных поровну.

Что и требовалось доказать.

Второй вариант

Рассуждение то же, меняются только числа. Делители $M$ разбиваются на пары $d$ и $\frac{M}{d}$, и двести наименьших делителей — в паре с двумястами наибольшими: Саша стёр $200$ целых пар.

Если бы $M$ было нечётным, после стирания осталось бы больше $800 - 400 = 400$ нечётных делителей и ни одного чётного — не поровну. Значит, $M$ чётное, пар из двух нечётных делителей нет, а средний делитель квадрата, если он есть, чётный. Как в шаге 4, «поровну» после стирания по $200$ означает, что остались только пары «чётное и нечётное».

Стирание по $400$ убирает ещё $200$ таких пар, а оставшиеся по-прежнему «чётное и нечётное», поэтому чётных и нечётных снова поровну. Условие «больше $800$ делителей» нужно, чтобы по $400$ с каждого края стереть было можно.

Пример: $M = 2\cdot 3^4\cdot 5^3\cdot 7^2\cdot 11\cdot 13\cdot 17 = 2\,412\,159\,750$ имеет $960$ делителей; после стирания по $200$ остаётся по $280$ чётных и нечётных, после стирания по $400$ — по $80$.