28-я Балканская математическая олимпиадаЯссы, Румыния, 2011 год

Пусть $S$ конечное множество натуральных чисел, которое имеет следующее свойство: если $x$ — элемент $S$, то и все положительные делители $x$ также принадлежат $S$. Непустое подмножество $T$ множества $S$ назовем хорошим, если для любых чисел $x, y\in T$ и $x < y$ отношение $y/x$ является степенью простого числа. Непустое подмножество $T$ множества $S$ назовем плохим, если для любых чисел $x, y\in T$ и $x < y$, отношение $y/x$ не является степенью простого числа. Условимся, что одноэлементное подмножество $S$ одновременно является и хорошим и плохим. Пусть $k$ максимально возможный размер хорошего подмножества $S$. Докажите, что $k$ также является наименьшим числом попарно-непересекающихся плохих подмножеств, объединение которых дает множество $S$.

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

Пусть $p_1,p_2,\ldots,p_s$ — все простые числа, делящие любой элемент $S$. Тогда элемент $x$ из $S$ можно записать как $x=\prod_{i=1}^s p_i^{x_i}$, где $0 \leq x_i \leq \alpha_i$ (где $\alpha_i$ — это наибольший показатель простого числа $p_i$ по всем элементам $S$). Фактически мы будем отождествлять $x$ с $s$-набором $(x_1,x_2,\ldots,x_s)$.

Определить отношение $y\prec x$, имея все $y_i = x_i$, за исключением одного индекса $j$, для которого $y_j\leq x_j$, не работает, поскольку не обеспечивается транзитивность (например, $ (0,0) \prec (0,1) \prec (1,1)$, но $(0,0) \not \prec (1,1)$), и поэтому отношение не является частичным порядком. Таким образом, сказанное выше не позволяет использовать теорему Дилворта.

Несложный анализ структуры хорошего множества показывает, что для любого индекса $j$, для которого $\alpha_j = \max_{1\leq i\leq s} \alpha_i = \alpha$, он может иметь только вид $\{(x_1,\ldots,x_j,\ldots,x_s) \mid x_j = 0,1,\ldots,\alpha\}$, поэтому наибольший размер равен $k=\alpha+1$.

Теперь мы можем определить $y \prec x$, имея все $y_i = x_i$, за исключением одного индекса $j$, для которого $y_j \leq x_j$, а также $\left \lfloor \dfrac {1} {k} \sum_{i=1}^s y_i \right \rfloor = \left \lfloor \dfrac {1} {k} \sum_{i=1}^s x_i

\right \rfloor$. Это отношение частичного порядка с наибольшей цепью размера $k$ (некоторые, но не все хорошие множества являются цепочками в соответствии с этим отношением). Легко увидеть, что все антицепи являются плохими множествами, поэтому теорема Дилворта дает ответ - но на самом деле это делается задним числом, зная, что мы ищем, поскольку одно покрытие, созданное $k$ bad, устанавливает $B_0,B_1,\ ldots,B_{k-1}$ можно сделать, выбрав $B_r = \left \{ x \mid \sum_{i=1}^s x_i \equiv r \pmod{k}\right \}$ для $0 \leq r\leq k-1$, следовательно, в Дилворте нет реальной необходимости.