Решения: Дистанционные олимпиады, Азиатско-Тихоокеанская математическая олимпиада

Азиатско-Тихоокеанская математическая олимпиада, 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!.$