Loading [MathJax]/jax/output/SVG/jax.js

Азия-тынық мұхит математикалық олимпиадасы, 2014 жыл


S={1, 2, , 2014} болсын. S жиынының барлық бос емес TS ішкі жиын үшін, оның өкілі ретінде бір элемент таңдап алынуы керек. S жиынының барлық бос емес ішкі жиындарының өкілін таңдап алудың және келесі шартты қанағаттандыратын барлық тәсілдерсанын анықта: егер қандай-да бір DS ішкі жиыны, өзара қиылыспайтын бос емес A,B,CS ішкі жиындарының бірігуі болса, онда D жиынының өкілі кемінде A, B, C жиындарының біреуінің өкілі болу керек. ( Warut Suksompong )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Ответ.1082014!.
Решение. Для каждого подмножества X обозначим через r(X) представителя X. Положим x1=r(S). Сначала докажем следующий факт:

Если x1X и XS, то x1=r(X).
Если |X|2012, то мы можем представить S как объединение X и еще двух подмножеств S, причем попарные пересечения в этой тройке будут пустыми, это дает x1=r(X). Если |X|=2013, то возьмем yX и yx1. Мы можем представить X как объединение {x1,y} и еще двух подмножеств. Нами уже доказано, что r({x1,y})=x1 (поскольку |{x1,y}|=2<2012) и это означает, что yr(X) для всех yX кроме x1. Факт доказан.
Заметим, что это утверждение верно и в случае, когда множество S содержит не менее 5 элементов.
Существует ровно 2014 способов выбрать x1=r(S) и для x1XS имеем r(X)=x1. Пусть S1=S{x1}. Аналогично, мы можем утверждать, что существует ровно 2013 способов выбора x2=r(S1) и для x2XS1 имеем r(X)=x2. Аналогично, продвигаясь дальше, существует ровно 201420135 способов выбора x1,x2,,x2010S так, чтобы для всех i=1,2,,2010, xi=r(X) для каждого XS{x1,,xi1} и xiX.
У нас остается четырехэлементное множество Y={y1,y2,y3,y4}. Существует ровно 4 способа выбора r(Y). Пусть y1=r(Y). Тогда очевидно, что y1=r({y1,y2})=r({y1,y3})=r({y1,y4}). Только у подмножеств {y1,y2,y3}, {y1,y2,y4}, {y1,y3,y4}, {y2,y3,y4}, {y2,y3}, {y2,y4}, {y3,y4} еще не указаны представители. Их мы можем выбрать как угодно, что дает нам 3423 способов.
Итак, общее число возможных назначений представителей равно 2014201343423=1082014!.