We want to place $2012$ pockets, including variously colored balls, into $k$ boxes such that either
- For all boxes, all pockets in a box must include a ball with the same color
or
- For all boxes, all pockets in a box must include a ball having a color which is not included in any other pockets in this box
Find the smallest value of $k$ for which we can always do this placement whatever the number of balls in the pockets and whatever the colors of balls.
I will show that $k>44$.
Let all pockets be monochrome.
Let $p_1, p_2, \dots , p_{45}$ have color $c_1$.
Similarly, $p_{46}, p_{47}, \dots , p_{90}$ have color $c_2$.
$\vdots$
And, $p_{1981}, p_{1982}, \dots, p_{2012}$ have color $c_{45}$.
If you want to satisfy the first condition, you should put all pockets with color $c_i$ into $k_i$. So there should be $45$ boxes.
If you want to satisfy the second condition, you should put each pocket with color $c_i$ into a separate box. So there should be $45$ boxes. So $k > 44$. But I didn't proved that $k=45$.
I think the problem is related with Dilworth's Lemma or something similar to it. But I couldn't manage to set a proper (reflexive, transitive and antisymmetric) relation to get a partially ordered set to simulate the chains and the anti-chains.
Explanation:
Thinking pockets as sets ($p$), colors as elements ($c$), and boxes as sets of sets ($b$)
$p_i = \{c_{i1}, c_{i2}, \dots \}$ $b_i = \{p_{i1}, p_{i2}, \dots \}$
The problems asks for the least $k$ such that
$b_1 \cup b_2 \cup \dots \cup b_k = \{p_1, p_2, \dots, p_{2012}\}$ where $b_i \cap b_j = \emptyset$, for any $i \neq j$.
and all $b_i$s (all together) should satisfy one of the statements below:
For each $i$, it should be that $\bigcap\limits_{p \in b_i}p \neq \emptyset$
For each $i$, and each $j$ where $p_j \in b_i$, it should be that $p_j - \bigcup\limits_{p\in (b_i-p_j)}^{}p \neq \emptyset$