|
|
 |
Условие
Назовём набор из $k$ последовательных натуральных чисел хорошим, если можно у каждого из этих чисел выбрать по простому делителю так, чтобы у всяких двух разных чисел были выбраны разные делители. В противном случае назовём набор плохим. При всяком ли натуральном $k$ количество плохих наборов из $k$ последовательных натуральных чисел конечно?Решение
Для $k=1$ ясно, что существует ровно один плохой набор, который состоит только из единицы. Для $k \geqslant 2$ будем доказывать, что набор $n+1, n+2, \dots, n+k$ является хорошим при любом натуральном $n > k^k$.Заметим, что любые два числа из этого набора не могут иметь общего делителя, большего $k$. Действительно, если бы такой делитель существовал, то он делил бы и разность этих чисел, которая меньше $k$, что невозможно.
Разобьём числа набора на две группы. В первую группу включим числа, имеющие простой делитель, больший $k$, во вторую – остальные. Каждому числу первой группы сопоставим любой его простой делитель, больший $k$. Эти простые делители различны, поскольку в противном случае два числа имели бы общий делитель, больший $k$.
Обозначим через $p_1, \dots, p_m$ все простые числа, не превосходящие $k$. Тогда каждое число второй группы представляется в виде $p_1^{\alpha_1}\dots p_m^{\alpha_m}$, где $\alpha_i \geqslant 0$. Для каждого такого числа выберем простой делитель $p_i$, для которого величина $p_i^{\alpha_i}$ максимальна среди всех $p_1^{\alpha_1}, \dots, p_m^{\alpha_m}$.
Покажем, что для выбранного $i$ выполнено $p_{\smash i}^{\alpha_i} > k$. Действительно, если бы для всех $i$ было выполнено $p_{\smash i}^{\alpha_i} \leqslant k$, то всё число не превосходило бы $k^k$, что противоречит условию $n > k^k$. Теперь докажем, что выбранные простые делители не совпадают. Действительно, если одно из чисел набора делится на $p^{\alpha} > k$, а другое число набора делится на $p^{\beta} > k$, то у этих двух чисел есть общий делитель $p^{\min(\alpha,\beta)} > k$, что невозможно.
Ясно, что двум числам из разных групп также сопоставлены разные простые делители. Получаем, что все плохие наборы содержатся среди наборов с $n \leqslant k^k$, а значит, их конечное число.
Ответ
Да, количество плохих наборов конечно для любого натурального $k$.Замечания
- Условие задачи можно переформулировать на языке теории графов. Построим двудольный граф, в котором вершины первой доли соответствуют числам набора, а вершины второй доли – простым делителям этих чисел. Соединим вершину числа и вершину простого числа ребром тогда и только тогда, когда это число делится на данный простой делитель. В такой формулировке задача сводится к поиску паросочетания, покрывающего все вершины первой доли. Это, в частности, связано с теоремой Холла о паросочетаниях в двудольных графах.
- На Турнире городов 2026 года задача предлагалась в следующей формулировке:
Назовём набор из $k$ последовательных натуральных чисел неудачным, если невозможно у каждого из этих чисел выбрать по простому делителю так, чтобы среди выбранных делителей не было одинаковых. При каждом ли натуральном $k$ количество неудачных наборов из $k$ последовательных натуральных чисел конечно?
