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


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

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

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

Если $x_1 \in X$ и $X \subseteq S$, то $x_1 = r(X)$.
Если $|X| \le 2012,$ то мы можем представить $S$ как объединение $X$ и еще двух подмножеств $S$, причем попарные пересечения в этой тройке будут пустыми, это дает $x_1 = r(X)$. Если $|X| = 2013,$ то возьмем $y \in X$ и $y \ne x_1$. Мы можем представить $X$ как объединение $\{x_1,y \}$ и еще двух подмножеств. Нами уже доказано, что $r(\{x_1,y \}) = x_1$ (поскольку $|\{x_1,y \}| = 2 < 2012$) и это означает, что $y \ne r(X)$ для всех $y \in X$ кроме $x_1$. Факт доказан.
Заметим, что это утверждение верно и в случае, когда множество $S$ содержит не менее $5$ элементов.
Существует ровно 2014 способов выбрать $x_1 = r(S)$ и для $x_1 \in X \subseteq S$ имеем $r(X) = x_1$. Пусть $S_1 = S \setminus \{ x_1\}$. Аналогично, мы можем утверждать, что существует ровно $2013$ способов выбора $x_2 = r(S_1)$ и для $x_2 \in X \subseteq S_1$ имеем $r(X) = x_2$. Аналогично, продвигаясь дальше, существует ровно $2014 \cdot 2013 \cdot \dots \cdot 5$ способов выбора $x_1,x_2, \ldots, x_{2010} \in S$ так, чтобы для всех $i = 1, 2, \ldots, 2010$, $x_i = r(X)$ для каждого $X\subseteq S \setminus \{x_1, \ldots, x_{i-1} \}$ и $x_i \in X$.
У нас остается четырехэлементное множество $Y = \{y_1, y_2, y_3, y_4\}$. Существует ровно $4$ способа выбора $r(Y)$. Пусть $y_1 = r(Y)$. Тогда очевидно, что $y_1 = r(\{y_1, y_2 \}) = r(\{y_1, y_3 \})=r(\{y_1, y_4 \}).$ Только у подмножеств $\{ y_1, y_2, y_3\},$ $\{ y_1, y_2, y_4\},$ $\{ y_1, y_3, y_4\},$ $\{ y_2, y_3, y_4\},$ $\{y_2, y_3\},$ $\{ y_2, y_4\},$ $\{ y_3, y_4\}$ еще не указаны представители. Их мы можем выбрать как угодно, что дает нам $3^4 \cdot 2^3$ способов.
Итак, общее число возможных назначений представителей равно $2014 \cdot 2013 \cdot \dots \cdot 4 \cdot 3^4 \cdot 2^3 = 108 \cdot 2014!.$