Азиатско-Тихоокеанская математическая олимпиада, 2014 год


Пусть $S = \{ 1,2,\ldots, 2014\}.$ Для каждого непустого подмножества $T \subseteq S$ должен быть выбран один из его элементов в качестве его $\it представителя$. Найдите количество всех способов выбора представителей для всех непустых подмножеств $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!.$