Russia — Regional Round

Установим следующее описание удачных чисел.

Лемма. Число $b$ является удачным тогда и только тогда, когда каждое простое число входит в разложение $b$ на простые множители с одним из следующих показателей: $0, 1, 2, 3, 4, 6, 8$.

Доказательство. Назовем целое неотрицательное число $k$ счастливым, если не существует такого целого $m$, что $2m < k \le \frac{5}{2}m$. Заметим, что счастливыми являются в точности числа $0, 1, 2, 3, 4, 6, 8$. Действительно, при $k \le 8$ в этом можно убедиться прямой проверкой. Если же $k \ge 9$, то выберем максимальное число $m$ такое, что $2m < k$. Тогда $m \ge 4$, и $\frac{5}{2}m \ge 2m+2 = 2(m+1) \ge k$ по выбору $m$, то есть $k$ несчастливо. Осталось показать, что $b$ удачно тогда и только тогда, когда каждое простое число входит в разложение $b$ со счастливым показателем.

Пусть число $b$ неудачно, то есть $a^5 : b^2, a^2 : b$ для некоторого $a$. Тогда некоторое простое $p$ входит в разложение $a^2$ в меньшей степени, чем в разложение $b$. Пусть $p$ входит в разложение $a$ и $b$ в степенях $m$ и $k$ соответственно; тогда $2m < k$, но $\frac{5}{2}m \ge k$, так как $a^5 : b^2$. Значит, число $k$ — несчастливое.

Итак, если все степени вхождения простых чисел в $b$ счастливы, то $b$ удачно. В противном же случае, если $b = p^k b'$, где $b'$ не делится на $p$ и $k$ несчастливо ($2m < k \le \frac{5}{2}m$), то при $a = p^m b'$ число $a^5$ делится на $b^2$, а $a^2$ не делится на $b$, и $b$ неудачно. Лемма доказана. $\Box$

Подсчитаем теперь количество неудачных натуральных чисел, меньших $2010$. Согласно лемме, надо подсчитать количество чисел, имеющих простой делитель, входящий в разложение на простые множители с показателем $5, 7, 9$ или более $9$. Поскольку $2^{10} < 2010 < 2^{11}$, $3^6 < 2010 < 3^7$, $2^5 \cdot 3^5 > 2010$ и $5^5 > 2010$, каждое неудачное число, меньшее $2010$, принадлежит к одному из следующих непересекающихся классов:

1) числа вида $2^5q$, где $q$ — нечётное и $q \le 61$ (поскольку $2^5 \cdot 61 < 2010 < 2^5 \cdot 63$);

2) числа вида $2^7q$, где $q$ — нечётное и $q \le 15$ (поскольку $2^7 \cdot 15 < 2010 < 2^7 \cdot 17$);

3) числа вида $2^9q$, где $q = 1$ или $q = 3$ (поскольку $q$ нечетно, и $2^9 \cdot 3 < 2010 < 2^9 \cdot 5$);

4) число $2^{10}$;

5) числа вида $3^5q$, где $q$ не делится на $3$ и $q \le 8$ (поскольку $3^5 \cdot 8 < 2010 < 3^5 \cdot 10$).

Итого мы получаем ровно $31$ число из класса 1, ровно $8$ чисел из класса 2, ровно $2$ числа из класса 3, ровно одно число из класса 4 и ровно $6$ чисел из класса 5. Таким образом, общее количество неудачных чисел, меньших $2010$, равно $31 + 8 + 2 + 1 + 6 = 48$. Тогда количество удачных чисел равно $2009 - 48 = 1961$.