Математикадан 28-ші Балкан олимпиадасы, Яссы, Румыния, 2011 жыл

$S$ жиыны келесідей қасиеттер орын алатын ақырлы натурал сандар жиыны болсын: егер $x$ — $S$ жиынының элементі болса, онда $x$-тің барлық оң бөлгіштері де $S$ жиынында жатады. $S$ жиынының бос емес $T$ ішкі жиынын жақсы деп айтамыз, егер кез келген $x, y\in T$ және $x < y$ сандары үшін $y/x$ қатынасы жай санның дәрежесі болса. $S$ жиынының бос емес $T$ жиынын жаман деп айтамыз, егер кез келген $x, y\in T$ және $x < y$ сандары үшін $y/x$ қатынасы жай санның дәрежесі болмаса. $S$ жиынының бір элементі бар ішкі жиынын жақсы да жаман да деп келісейік. $S$ жиынының жақсы ішкі жиынының мүмкін болатын ең үлкен өлшемі $k$ болсын. Бірігуі $S$ жиынын беретін өзара-қиылыспайтын жаман ішкі жиындардың ең кіші саны $k$ болатынын дәлелдеңіздер.

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

Пусть $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$, следовательно, в Дилворте нет реальной необходимости.