Олимпиадная задача по теории чисел и комбинаторике для 9-10 классов от Кожевникова П. А.

 Лемма. Числоbявляется удачным тогда и только тогда, когда каждое простое число входит в разложениеbна простые множители с одним из следующих показателей: 0, 1, 2, 3, 4, 6, 8.  Доказательство. Назовем целое неотрицательное числоk счастливым, если не существует такого целогоm, что   2m < k≤ 2,5m.   Заметим, что счастливыми являются в точности числа 0, 1, 2, 3, 4, 6, 8. При  k≤ 9  в этом можно убедиться прямой проверкой. Если же  k> 9,  то выберем такое максимальное числоm, что  2m < k.  Тогда  m> 4,  и  2,5m> 2m+ 2 = 2(m+ 1) >k   по выборуm, то естьkнесчастливо.   Пусть числоbнеудачно, то естьa⁵делится наb², ноa² не делится наbдля некоторогоa. Тогда некоторое простоеpвходит в разложениеa²в меньшей степени, чем в разложениеb. Пустьpвходит в разложенияaиbв степеняхmиkсоответственно; тогда  2m < k,  но  5m≥ 2k.  Значит, числоk– несчастливое. Итак, если все степени вхождения простых чисел вbсчастливы, тоbудачно.   Если же  b = p^kb',  гдеb'не кратноpиkнесчастливо  (2m < k≤ 2,5m),  то при  a = p^mb'  числоa⁵делится наb², аa² не делится наb, то естьbнеудачно.   Согласно лемме, каждое неудачное число имеет простой делитель, входящий в разложение на простые множители с показателем 5, 7 или более 8. Поскольку  2¹⁰ < 2010 < 2¹¹,  3⁶ < 2010 < 3⁷,  2⁵·3⁵ > 2010  и  5⁵ > 2010,  каждое неудачное число, меньшее 2010, принадлежит одному из следующих непересекающихся классов:

  1) числа вида 2⁵q, где q нечётно и  q ≤ 61  (2⁵·61 < 2010 < 2⁵·63);

  2) числа вида 2⁷q, где q нечётно и  q ≤ 15  (2⁷·15 < 2010 < 2⁷·17);

  3) числа вида 2⁹q, где  q = 1 или 3  (2⁹·3 < 2010 < 2⁹·5);

  4) число 2¹⁰;

  5) числа вида 3⁵q, где q не кратно 3 и  q ≤ 8  (3⁵·8 < 2010 < 3⁵·10).

  Таким образом, общее количество неудачных чисел, меньших 2010, равно  31 + 8 + 2 + 1 + 6 = 48,  а количество удачных чисел равно

2009 – 48 = 1961.

Ответ задачи отсутствует