Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

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


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

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

  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)(1,1)), и поэтому отношение не является частичным порядком. Таким образом, сказанное выше не позволяет использовать теорему Дилворта.

Несложный анализ структуры хорошего множества показывает, что для любого индекса j, для которого αj=max, он может иметь только вид \{(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$, следовательно, в Дилворте нет реальной необходимости.