Rainbow covering by rectangles There are $n$ coverings of the unit square, each of which contains $k$ axes-parallel rectangles of a unique color.
Define a rainbow covering as a covering of the unit square that contains exactly one rectangle of each color.
Given $k$, what is the smallest $n$ for which a rainbow covering always exists?
For $k=2$, a rainbow covering might not exist if $n=2$, since we might have a covering by blue "vertical" rectangles and another covering by red "horizontal" rectangles, and each pair of one blue and one red rectangle does not cover the entire unit square. However, when $n=3$, there are at least two horizontal pairs or two vertical pairs, and taking one rectangle of each of these coverings (plus an arbitrary one from the third covering) yields a rainbow covering of the unit square. So for $k=2$ the answer is $3$.
What is the smallest $n$ for $k\geq 3$?
 A: I am impressed by your problem inventiveness.
For each natural $k$ let $n(k)$ be the smallest $n$ for which a rainbow covering always exists.
Proposition. $n(k)\le k(k+1)/2$.
Consider first a one-dimensional counterpart of $n(k)$.
Lemma.  Given coverings $\mathcal C_1,\dots, \mathcal C_k$ of the unit segment $I$ by $k$ its subsegments, we can choose a segment $I_i\in\mathcal C_i$ for each $i=1,\dots, k$ such that $\bigcup_{i=1}^k I_i=I$.
Proof. We use induction with respect to $k$. The lemma is obvious when $k=1$. Suppose that the lemma is already proved for $k$. Let  we have coverings $\mathcal C_1,\dots, \mathcal C_{k+1}$ of $I$ by $k+1$ its subsegments. For each $i=1,\dots, k+1$ we have $[0,x_i]\in \mathcal C_i$  for some $x_i\in (0,1]$. Let $x_j$ be maximal of the numbers $x_i$. Pick a segment $I_j=[0,x_j]$ of $\mathcal C_j$ and remark that for each $i\ne j$, $\mathcal C_j\setminus [0,x_i]$ is a covering of $[x_j,1]$ by $k$ segments. By the induction hypothesis, we can pick a segment $I_i\in\mathcal C_i$ for each $i\ne j$ providing that $[x_j,1]\subset\bigcup_{i\ne j} I_i$. Then $$I=[0, x_j]\cup [x_j,1]\subset I_j\cup \bigcup_{i\ne j} I_i=\bigcup_{i=1}^{k+1} I_i. \square$$
Proof of Proposition. We use induction with respect to $k$. The proposition is obvious when $k=1$. Suppose that the proposition already proved for $k$. Let $n=(k+1)(k+2)/2$ and we have coverings $\mathcal C_1,\dots, \mathcal C_n$ of a unit square $I^2$ by $k+1$ its subrectangles. For each $i=1,\dots, n$ let $x_i=\min\{y: [0,y]\times [a,b]\in \mathcal C_i$ for some $a<b\}$. Renaming $\mathcal C_i$, if necessarily, we can assure that $x_1\le x_2\le\dots\le x_n$. Put $n’=k(k+1)/2+1$. Lemma implies that we can pick a rectangle $R_i=[0, y_i]\times [a_i, b_i]\in\mathcal C_i$ for each $i=n’,n’+1,\dots n’+k=n$ providing $[0,1]=\bigcup_{i=n’}^n [a_i, b_i]$. Since $y_i\ge x_i\ge x_{n’}$ for each $i\ge n’$, we have $$[0, x_{n’}]\times [0,1]\subset \bigcup_{i=n’}^n [0, x_i]\times [a_i, b_i]\subset \bigcup_{i=n’}^n R_i.$$
For each $i=1,\dots n’-1$, pick $R’_i=[0,x_i]\times [a_i,b_i]\in\mathcal C_i$ and remark that $\mathcal C_i’=\mathcal C_i\setminus R’_i$ is a covering of $[x_{n’},1]\times [0,1]$ by $k$ rectangles. By the induction hypothesis, we can pick a rectangle $R_i\in\mathcal C_i’$ for each $i=1,\dots n’-1$ providing  $[x_{n’},1]\times [0,1]\subset\bigcup_{i=1}^{n’-1} R_i$. Then
$$I^2=[0, x_{n’}]\times [0,1]\cup [x_{n’},1]\times [0,1]\subset \bigcup_{i=n’}^n R_i\cup \bigcup_{i=1}^{n’-1} R_i=\bigcup_{i=1}^{n} R_i.$$
