Processing math: 72%

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


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

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

  8
1 года 4 месяца назад #

Пусть p1,p2,,ps — все простые числа, делящие любой элемент S. Тогда элемент x из S можно записать как x=si=1pxii, где 0xiαi (где αi — это наибольший показатель простого числа pi по всем элементам S). Фактически мы будем отождествлять x с s-набором (x1,x2,,xs).

Определить отношение yx, имея все yi=xi, за исключением одного индекса j, для которого yjxj, не работает, поскольку не обеспечивается транзитивность (например, (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$, следовательно, в Дилворте нет реальной необходимости.