Problem 2109

We will prove that each $n \in \{33, 34, \dots, 2^{14}\}$ is a solution.

We begin by noticing that if we have a painting $T_i$ in the museum that uses $k$ colors, the painting that uses the other $15-k$ colors cannot be in the museum. Therefore, out of the $2^{15}-1$ possible paintings that can be obtained with the 15 colors, we have a maximum of $2^{14}$ paintings in the museum, and the maximum can be achieved if we consider all paintings that use color $c_1$ together with all $2^{14}$ subsets of colors $\{c_2, \dots, c_{15}\}$.

We show that for any $33 \le n \le 2^{14}$, we can find the paintings $T_1, T_2, T_3, T_4$ with the properties described in the problem. By $T_i \cap T_j$ and $T_i \cup T_j$ we mean the set of colors that are common to the paintings $T_i$ and $T_j$, and the set of all colors used in the paintings $T_i$ and $T_j$, respectively. We need to prove that there exist $i_1, i_2, i_3, i_4 \in \{1, 2, \dots, n\}$ such that:
$$(T_{i_1} \cap T_{i_2}) \subset T_{i_3} \cup T_{i_4}$$
Assuming that for any choice of $i < j$ and $k < \ell$ from $\{1, 2, \dots, n\}$ with $\{i, j\} \cap \{k, \ell\} = \emptyset$, we have:
$$|(T_i \cap T_j) \setminus (T_k \cup T_\ell)| \ge 1.$$
Studying the sum:
$$S = \sum_{\substack{1 \le i < j \le n \\ 1 \le k < \ell \le n \\ \{i,j\} \cap \{k,\ell\} = \emptyset}} |(T_i \cap T_j) \setminus (T_k \cup T_\ell)|,$$
we notice that this sum has $\binom{n}{2} \cdot \binom{n-2}{2}$ terms, each of which is greater than or equal to 1, so we obtain:
$$S \ge \frac{n(n-1)}{2} \cdot \frac{(n-2)(n-3)}{2}.$$

Let's count the number of occurrences of each color $c_m$, where $m = \overline{1, 15}$, and let $n_m$ be the number of paintings $T_i$ that contain color $c_m$. To have $c_m \in (T_i \cap T_j) \setminus (T_k \cup T_\ell)$, we must have $c_m \in T_i, T_j$ and $c_m \notin T_k, T_\ell$. If $n_m \in \{0, 1, n-1, n\}$, then there is no tuple $(T_i, T_j, T_k, T_\ell)$ for which $c_m \in (T_i \cap T_j) \setminus (T_k \cup T_\ell)$. For $2 \le n_m \le n-2$, the pair $(T_i, T_j)$ can be chosen in $\binom{n_m}{2}$ ways, and the pair $(T_k, T_\ell)$ can be chosen in $\binom{n-n_m}{2}$ ways. Therefore, we have:
$$S = \sum_{\substack{m=1 \\ 2 \le n_m \le n-2}}^{15} \frac{n_m(n_m-1)}{2} \cdot \frac{(n-n_m)(n-n_m-1)}{2}.$$
From AM-GM we have $n_m(n - n_m) \le \left(\frac{n}{2}\right)^2$ and $(n_m - 1)(n - 1 - n_m) \le \left(\frac{n-2}{2}\right)^2$, from which we obtain:
$$\begin{aligned} S & \le \sum_{\substack{m=1 \\ 2 \le n_m \le n-2}}^{15} \frac{1}{4} \left(\frac{n}{2}\right)^2 \cdot \left(\frac{n-2}{2}\right)^2 \le 15 \cdot \frac{1}{4} \cdot \left(\frac{n}{2}\right)^2 \cdot \left(\frac{n-2}{2}\right)^2 < \\ & < \frac{n(n-1)}{2} \cdot \frac{(n-2)(n-3)}{2}, \quad \forall n \ge 33, \end{aligned}$$
which is a contradiction. Therefore, for any $33 \le n \le 2^{14}$ we have four paintings with the property from the statement.