In an art museum, there are $n$ paintings, $n \ge 33$, for which there are
used a total of $15$ different colors so that any two paintings have at least one common color and there are no two paintings that have exactly the same colors. Determine all possible values of $n \ge 33 $ so that anyway we color the paintings with the above properties we can choose four distinct paintings $T_1$, $T_2$, $T_3$ and $T_4$, so that any color that is used in both $T_1$ and $T_2$, it can be found in $T_3$ or $T_4$.
I've been trying to solve this combinatorics problem for some time, but I can't think of what the result could be (probably a big number). I don't know if it will be useful, I will put my attempts below.
Let $T_1, T_2, T_3, … , T_n$ be the n sets representing the "paintings", each having at least one element and at most 15 elements and let those elements be $c_1,c_2,…,c_{15}$(the $15$ colors).From the first sentence we have that $T_i \ne T_j , \forall i,j = \{1,2,…,n\} , i \ne j$ and $T_i \cap T_j \ne \emptyset$ for every $i \ne j$
.From the second sentence $\implies \exists i,j,k,l \in \{1,2,…,n\}$ with $i \ne j \ne k \ne l $ such that $(T_i \cap T_j) \subset (T_k \cup T_l)$ (both and or in the second sentence were the key words from which I got this ) . The total number of paintings with no conditions is $2^{15}-1$ but we can't have 2 subsets which don't have any color in common so we would have $2^{14}$ paintings (for example we take the color $c_i$ and the subset $C=\{c_1,c_2,…,c_{15} \} \setminus \{c_i\}$ . For every subset of $C$ we put $c_i$ in it so we get the $2^{14}$).Now maybe we could show that for every $n\in \{33,34,…,2^{14}\} $ we can the find the 4 paintings with the second condition.I think if by absurd , let's say that $\forall i,j,k,l \in \{1,2,…,n\}$ with $i \ne j \ne k \ne l $ we have that $(T_i \cap T_j) \not\subset (T_k \cup T_l)$.Prety much I denied the second condition.So if we prove that the condition $|(T_i \cap T_j) \setminus (T_k \cup T_l)| \ge 1$ (equivalent to what I wrote previously) $\implies$ contradiction , we are done.
I don't really know what to do next, I think the answer would have to do with that "15 colors". I think that for a very large n we can no longer form these sets. What do you think ? I am open to any suggestion, comment or solution. Thank you !
Best Answer
I think I have an answer that relies crucially on there being exactly 15 colors (it won't work for 16 colors). I call the paintings $P_1, \cdots, P_n$.
We count the number of five tuples $$(i,j,k,l,c)$$ where $i,j,k,l$ are distinct integers in $1,2,\cdots, n$, and $c$ is a color such that $c$ lies in $P_i$ and $P_j$ but not $P_k$ or $P_l$. Call such a five tuple good.
On one hand, for each color $c$, suppose there are $a$ of the $P_i$'s that contain $c$, and $(n - a)$ of the $P_i$'s that doesn't. Then the number of good five tuples with color $c$ is $$a(a - 1)(n - a)(n - a - 1)$$ which by AM-GM is at most $n^2(n - 2)^2 / 16$. Summing over all the colors, the number of good five tuples is at most $$15 n^2(n - 2)^2 / 16.$$ On the other hand, suppose that for any four distinct painting $P_i, P_j, P_k, P_l$, we have $P_i \cap P_j \not\subset P_k \cup P_l$. Then there exists a color $c$ such that $(i,j,k,l,c)$ is a good five tuple. So the number of good five tuples is at least the number of four tuples of distinct paintings, which is $n(n - 1)(n - 2)(n - 3)$.
Now, $n \geq 33$ implies $$n(n - 1)(n - 2)(n - 3) > 15 n^2(n - 2)^2 / 16.$$ which gives a contradiction. So there are four distinct painting $P_i, P_j, P_k, P_l$ such that $P_i \cap P_j \subset P_k \cup P_l$. This works for any $n \geq 33$.
P.S. for $c$ colors in general I don't have an exact answer, but the number of paintings need to be at least $2^{\Theta(c)}$ by a random construction.