35-я Международная Математическая OлимпиадаГонконг, Гонконг, 1994 год

Показать, что существует множество $A$, состоящее из целых положительных чисел, которое обладает следующим свойством: для каждого бесконечного множества $S$ простых чисел существует целое число $k\ge 2$, а также существуют два целых положительных числа $m\in A$ и $n\notin A$ таких, что оба являются произведениями $k$ различных элементов множества $S$.

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

Красивая проблема. Давайте на мгновение посмотрим, что там говорится. Версия теоремы Рамсея гласит следующее: если мы раскрасим подмножества $k$-элементов $\mathbb N$ в два цвета (конечно, это работает для бесконечного числа цветов, но нас интересует именно этот случай) , то существует бесконечное $k$-однородное множество, т. е. бесконечное множество, все $k$-элементные подмножества которого имеют один и тот же цвет. Эта проблема говорит о том, что такой результат больше не обязательно верен, если мы попытаемся сделать это для всех $k\ge 2$ одновременно: если мы раскрасим все подмножества $\mathbb N$, которые имеют по крайней мере два элементы двух цветов, то не обязательно должно существовать бесконечное множество, $k$-однородное для всех $k$. Здесь, конечно, набор простых чисел представляет собой $\mathbb N$, а произведение $p_{i_1}\cdot\ldots\cdot p_{i_k}$ представляет набор $\{\i_1,\ldots,i_k\} $. Если произведение различных простых чисел (мы не работаем с числами, не свободными от квадратов) принадлежит набору, который мы хотим построить, мы скажем, что соответствующий набор красный, а если это не так, мы скажем, что соответствующий набор комплект синий. Вот почему с этого момента мы будем работать в этом режиме, используя подмножества $\mathbb N$ вместо положительных целых чисел без квадратов. Теперь мы докажем, что для $k\ge 2$ и некоторого $x\in\mathbb N$ мы можем найти двухцветную раскраску $k$-элементных подмножеств $\mathbb N$ такую, что $x$ принадлежит не существует бесконечного $k$-однородного множества. Это почти очевидно. Мы можем просто раскрасить все множества $k$-элементов, содержащие $x$, в красный цвет, а остальные — в синий. Мы назовем эту процедуру $P(x,k)$. Теперь, чтобы получить желаемое, мы можем применить процедуры $P(k,k)$ для всех $k\ge 2$. Другими словами, при полученной нами двухраскраске подмножеств $\mathbb N$, имеющих не менее $2$ элементов, $2$ не может принадлежать никакому бесконечному $2$-однородному множеству, $3$ не может принадлежать никакому бесконечному $3 $-однородное множество, и, вообще говоря, $n$ не может принадлежать никакому бесконечному $n$-однородному множеству. Другими словами, в $\mathbb N$ не существует бесконечных подмножеств, $k$-однородных для всех $k\ge 2$.

Сидит как будто это не первый коммент с АОПСа

только хотел написать

У вас решение не верно теорема не верна