Комбинаторная задачка из ru_math@lj

[maxal]

Есть матрица размера $n\times \frac{n(n-1)}2$. Строки проиндексированы числами от $1$ до $n$, столбцы -- парами таких чисел (числа в каждой паре разные). В клетке $[i, (j,k)]$ стоит одно из чисел $i, j, k$ (матрица, таким образом, задана неоднозначно), причём если $i=j$, то в клетке стоит обязательно $k$, а если $i=k$, то в клетке стоит обязательно $j$. Одноцветным прямоугольником относительно этой матрицы называется такая её подматрица, в которой во всех клетках стоит одно и то же число.

Доказать, что для любой такой матрицы кол-во одноцветных прямоугольников, необходимых для покрытия всей матрицы, не меньше $c n \log n$ для некоторой константы $c>0$.

Отсюда. Там же приведен пример для $n=8.$