28-я Балканская математическая олимпиада
Яссы, Румыния, 2011 год
Комментарий/решение:
Пусть p1,p2,…,ps — все простые числа, делящие любой элемент S. Тогда элемент x из S можно записать как x=∏si=1pxii, где 0≤xi≤αi (где αi — это наибольший показатель простого числа pi по всем элементам S). Фактически мы будем отождествлять x с s-набором (x1,x2,…,xs).
Определить отношение y≺x, имея все yi=xi, за исключением одного индекса j, для которого yj≤xj, не работает, поскольку не обеспечивается транзитивность (например, (0,0)≺(0,1)≺(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$, следовательно, в Дилворте нет реальной необходимости.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.