Натуральное число \(N\) имеет больше \(1000\) натуральных делителей (включая \(1\) и \(N\)). Все эти делители выписаны на доске. Саша стёр \(250\) наибольших и \(250\) наименьших из них. Среди оставшихся делителей оказалось поровну делящихся на \(13\) и не делящихся на \(13\). Докажите, что среди всех делителей тоже поровну делящихся и не делящихся на \(13\).

Решение

1. Свойство количества делителей

По условию, среди оставшихся \(T-500\) делителей количество делящихся на 13 равно количеству не делящихся на 13. Это означает, что \(T-500\) должно быть чётным числом. Следовательно, \(T\) (общее количество делителей) тоже должно быть чётным.

\[
\text{Число имеет чётное количество делителей} \iff \text{оно не является полным квадратом}
\]

Значит, \(N\) не является полным квадратом.

2. Парность делителей

Если \(N\) не является полным квадратом, то все его делители \(d\) можно разбить на пары \((d, N/d)\), где \(d \neq N/d\). Если мы упорядочим все делители \(d_1 < d_2 < \ldots < d_T\), то:

\[
d_i \cdot d_{T-i+1} = N
\]

При этом 250 наименьших делителей \(\{d_1, \ldots, d_{250}\}\) образуют пары с 250 наибольшими делителями \(\{d_{T-249}, \ldots, d_T\}\). То есть, если \(d\) — один из 250 наименьших делителей, то \(N/d\) — один из 250 наибольших, и наоборот.

3. Определяем, делится ли \(N\) на 13

Если бы \(N\) не делилось на 13, то ни один из его делителей не мог бы делиться на 13. В этом случае среди оставшихся делителей не было бы ни одного, делящегося на 13. По условию, их поровну, значит, количество не делящихся на 13 также было бы равно нулю.

\[
T-500 = 0 \Rightarrow T=500
\]

Но это противоречит условию \(T > 1000\).

Следовательно, число \(N\) обязательно делится на 13.

4. Связь между делимостью \(d\) и \(N/d\) на 13

Мы знаем, что \(N\) делится на 13, а 13 — простое число.

Рассмотрим любой делитель \(d\) числа \(N\):

\[
\text{Если } d \nmid 13 \text{, то из } N = d \cdot (N/d) \text{ и } 13 \mid N \text{ следует } 13 \mid (N/d)
\]

5. Подсчеты

Введём обозначения:

\[
\begin{aligned}
&N_{\text{min, 13}} - \text{количество делителей, делящихся на 13, среди 250 наименьших} \\
&N_{\text{min, не 13}} - \text{количество делителей, не делящихся на 13, среди 250 наименьших} \\
&N_{\text{ost, 13}} - \text{количество делителей, делящихся на 13, среди оставшихся} \\
&N_{\text{ost, не 13}} - \text{количество делителей, не делящихся на 13, среди оставшихся}
\end{aligned}
\]

Из пункта 4 следует, что каждый из \(N_{\text{min, не 13}}\) делителей (которые не делятся на 13) в паре с \(N/d\) дает делитель из 250 наибольших, который делится на 13.

\[
\text{Количество делящихся на 13 среди 250 наибольших} = N_{\text{min, не 13}}
\]

Аналогично, если \(d\) — один из 250 наибольших делителей, который не делится на 13, то \(N/d\) — один из 250 наименьших, который делится на 13.

Теперь соберем общее количество делителей, делящихся на 13, и не делящихся на 13, среди всех \(T\) делителей.

Общее количество делителей, делящихся на 13:
\[
C_{13} = N_{\text{min, 13}} + (\text{количество делящихся на 13 среди 250 наибольших}) + N_{\text{ost, 13}}
\]
\[
C_{13} = N_{\text{min, 13}} + N_{\text{min, не 13}} + N_{\text{ost, 13}}
\]

Общее количество делителей, не делящихся на 13:
\[
C_{\text{не 13}} = N_{\text{min, не 13}} + (\text{количество не делящихся на 13 среди 250 наибольших}) + N_{\text{ost, не 13}}
\]
\[
C_{\text{не 13}} = N_{\text{min, не 13}} + N_{\text{min, 13}} + N_{\text{ost, не 13}}
\]

Мы знаем, что по условию \(N_{\text{ost, 13}} = N_{\text{ost, не 13}}\).

Сравнивая выражения для \(C_{13}\) и \(C_{\text{не 13}}\):
\[
C_{13} = (N_{\text{min, 13}} + N_{\text{min, не 13}}) + N_{\text{ost, 13}}
\]
\[
C_{\text{не 13}} = (N_{\text{min, 13}} + N_{\text{min, не 13}}) + N_{\text{ost, не 13}}
\]

Так как выражения в скобках одинаковы и \(N_{\text{ost, 13}} = N_{\text{ost, не 13}}\), то:
\[
C_{13} = C_{\text{не 13}}.
\]