Let $t$ be the number of colors, and call them $c_1, c_2, \cdots, c_t.$ For a color $c_i$, we will define its contribution to be the number of rows with a cell of this color plus the number of columns with a cell of this color. We will denote this quantity by $n_i.$ Observe that if we were to prove that $\sum n_i > 66$, we would be done by the Pigeonhole Principle. Lemma. If $c_i$ appears $x$ times, then $n_i > \frac{6}{11} x.$ Proof. Let $a, b$ denote the number of rows, columns, respectively that $c_i$ appears in. Observe that $ab \ ge x$, since each of the $x$ cells must be in an intersection of one of the $a$ rows and one of the $b$ columns. This implies by AM-GM that $n_i = a + b \ge 2 \sqrt{x}.$ As $7 \le x \le 13$, this is enough to imply the lemma. $\blacksquare$ By the lemma, we have that $\sum n_i > \frac{6}{11} \cdot 121$ since the colors appear a combined $121$ times. We're done. $\square$

My solution is similar to the one above, but with an improved result of the $\textbf{Lemma}$, as the AM-GM is a weak bound. Basically let $a_{i}$ denote the number of colours, appearing in the $i$-th row and $b_{i}$ denote the number of colours, appearing in the $i$-th column. Then we want to see how much does each colour contribute to the sum $\sum\limits_{i=1}^{11} a_{i}+b_{i}$. Let the colours be $c_{1},c_{2},\ldots ,c_{n}$ and let $|c_{i}|$ denote the number of cells in that colour. Also, let $d_{i}$ denote the number of columns and rows, which the cells of colour $c_{i}$ occupy (i.e. the "contribution" to the sum). Then it's elementary to check that if $|c_{i}|\in \{7,8,9\}$, then $d_{i}\geq 6$, if $|c_{i}|\in \{10,11,12\}$, then $d_{i}\geq 7$ and if $|c_{i}|=13$, then $d_{i}\geq 8$. Let the number of the colours from the first group be $x$, from the second group $y$ and from the third group $z$. Then from what we've already mentioned we can conclude that: $$\sum\limits_{i=1}^{11} (a_{i}+b_{i})\geq 6x+7y+8z, \text{ but using the groups we can double count the number of cells and derive: }9x+12y+13z\geq 121$$$$\implies \sum\limits_{i=1}^{11} (a_{i}+b_{i})\geq 6x+7y+8z=\frac{1}{2}(9x+12y+13z)+(x+y+z)+\frac{1}{2}(x+z)\geq \frac{121}{2}+\frac{121}{13}>60+9>66$$which is a slightly stronger bound (and I hope it's correct). And we've proven the problem by the Pigeonhole Principle. Now I also wanted to find if the constant $4$ is optimal and it is (here is a table $11\times 11$ table in which each row and column has no more than $4$ different colours): \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 1 & 1 & 1 & 5 & 5 & 5 & 4 & 4 & 4 & 4\\ \hline 1 & 1 & 1 & 1 & 5 & 5 & 5 & 4 & 4 & 4 & 4\\ \hline 1 & 1 & 1 & $\blacksquare$ & 5 & 5 & 5 & $\blacksquare$ & 4 & 4 & 4\\ \hline 1 & 1 & $\blacksquare$ & $\blacksquare$ & 5 & 5 & 5 & $\blacksquare$ & $\blacksquare$ & 4 & 4\\ \hline 6 & 6 & 6 & 6 & 9 & 9 & 9 & 8 & 8 & 8 & 8\\ \hline 6 & 6 & 6 & 6 & 9 & 9 & 9 & 8 & 8 & 8 & 8\\ \hline 6 & 6 & 6 & 6 & 9 & 9 & 9 & 8 & 8 & 8 & 8\\ \hline 2 & 2 & $\blacksquare$ & $\blacksquare$ & 7 & 7 & 7 & $\blacksquare$ & $\blacksquare$ & 3 & 3\\ \hline 2 & 2 & 2 & $\blacksquare$ & 7 & 7 & 7 & $\blacksquare$ & 3 & 3 & 3\\ \hline 2 & 2 & 2 & 2 & 7 & 7 & 7 & 3 & 3 & 3 & 3\\ \hline 2 & 2 & 2 & 2 & 7 & 7 & 7 & 3 & 3 & 3 & 3 \\ \hline \end{tabular}