Западно-Китайская математическая олимпиада, 2005 год

Пусть $S = \{1, 2, 3, \ldots , 2005\}$. Найдите наименьшее $n$ такое, что среди любых $n$ попарно взаимнопростых чисел из $S$ есть хотя бы одно простое.

Комментарий/решение

Решение. Обозначим, как $t$ количество простых, меньших 45. Предположим $t+1$ попарно взаимнопростых чисел из множества $S$ составные. Рассмотрим множества их простых делителей - из взаимной простоты они не пересекаются. Если каждое из них имеет по крайней мере 1 элемент, меньший 45, то количество простых, меньших 45, не менее $t+1$.

Значит найдется число, у которого все простые делители больше 45, то есть оно само больше $45^2=2025$ - противоречие.

Теперь посчитаем $t$.

$$2,3,5,7,11,13,17,19,23,29,31,37,41,43$$ Значит $t=14$. В качестве примера для $t$ взаимнопростых чисел, среди которых нет простых, приведём квадраты выше написанных простых.

Ответ. $15$