Задача 5. Стёртые края

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

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

Чем больше делитель $d$, тем меньше его пара $\frac{N}{d}$. Поэтому, если идти по делителям от меньшего к большему, их пары пройдут те же делители от большего к меньшему: самый маленький делитель — в паре с самым большим, второй — с предпоследним и так далее. Например, у $90$:

Значит, $300$ наименьших делителей — в паре ровно с $300$ наибольшими: Саша стёр $300$ пар целиком, и оставшиеся делители тоже складываются в целые пары. Только если $N$ — квадрат, например $36 = 6\cdot 6$, средний делитель остаётся в паре сам с собой.

N чётное, и что значит «поровну»

Делителей больше $1200$, Саша стёр $600$, значит, осталось больше $600$.

Если бы $N$ было нечётным, все его делители были бы нечётными, и среди оставшихся не было бы ни одного чётного — не поровну. Значит, $N$ чётное.

Произведение двух нечётных чисел нечётно, а произведение чисел пары равно чётному $N$. Поэтому пар из двух нечётных делителей нет. Пары бывают двух видов: «чётное и нечётное» и «два чётных». Средний делитель квадрата, если он есть, чётный: квадрат нечётного числа нечётен.

Пусть осталось $x$ пар «чётное и нечётное» и $y$ пар «два чётных». Тогда нечётных осталось $x$, а чётных — $x + 2y$, и ещё один, если остался средний делитель. Поровну бывает, только если $y = 0$ и среднего нет. Итак, среди оставшихся только пары «чётное и нечётное», а все пары «два чётных» (и средний делитель) стёрты.

У $60$, например, после стирания по два остаётся пара $6$ и $10$ из двух чётных — и чётных пять, а нечётных три.

Пусть N делится на 4: где удвоения?

Наша цель — понять, что $N$ не делится на $4$. Предположим противное: $N$ делится на $4$.

Возьмём любой оставшийся нечётный делитель $d$. Двоек в разложении $d$ на простые множители нет, поэтому все двойки числа $N$ попадают в $\frac{N}{d}$, и $\frac{N}{d}$ делится на $4$. Тогда

Значит, $2d$ — делитель $N$, и его пара $\frac{N}{2d}$ чётная: $2d$ стоит в паре «два чётных» (или это средний делитель, если $2d = \frac{N}{2d}$).

По шагу 2 такие делители стёрты. Но $2d$ больше $d$, а $d$ больше всех $300$ стёртых наименьших — ведь $d$ остался. Поэтому $2d$ стёрт среди $300$ наибольших.

Так у $60 = 4\cdot 15$: нечётным $3$ и $5$ соответствуют $6$ и $10$ — как раз пара «два чётных», которая осталась и испортила равенство.

Удвоениям не хватает места

Оставшихся делителей больше $600$, и половина из них нечётные — значит, нечётных осталось больше $300$. Здесь и нужно, что делителей именно больше $1200$.

У разных $d$ удвоения $2d$ тоже разные. По шагу 3 все они стёрты среди $300$ наибольших — то есть больше $300$ разных чисел помещаются в $300$ мест. Так не бывает.

Противоречие показывает, что $N$ не делится на $4$. Вместе с шагом 2: $N = 2m$, где $m$ — нечётное число.

Среди всех делителей поровну

У числа $N = 2m$ с нечётным $m$ ровно одна двойка. Поэтому каждый его делитель — это либо нечётный делитель $f$ (он делит $m$), либо $2f$. Каждому нечётному делителю $f$ соответствует чётный $2f$, и каждый чётный делитель получается так ровно из одного нечётного. Значит, чётных и нечётных делителей поровну.

Например, у $90 = 2\cdot 45$: нечётные $1, 3, 5, 9, 15, 45$ и чётные $2, 6, 10, 18, 30, 90$.

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

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

Рассуждение то же, меняются только числа: Саша стёр $150$ пар целиком, осталось больше $600 - 300 = 300$ делителей.

$M$ чётное: иначе все оставшиеся нечётны. Пар «два нечётных» нет, поэтому «поровну» значит, что остались только пары «чётное и нечётное».

Если бы $M$ делилось на $4$, то для каждого оставшегося нечётного $d$ делитель $2d$ стоял бы в паре «два чётных» и был бы стёрт среди $150$ наибольших. Но нечётных осталось больше $\frac{300}{2} = 150$, а их удвоения различны — в $150$ мест они не помещаются.

Значит, $M = 2m$ с нечётным $m$, и соответствие $d \leftrightarrow 2d$ даёт поровну чётных и нечётных делителей. Например, $M = 2\cdot 3^4\cdot 5^2\cdot 7^2\cdot 11\cdot 13\cdot 17 = 482\,431\,950$ имеет $720$ делителей; после стирания по $150$ остаётся по $210$ чётных и нечётных.