Есть матрица размера

. Строки проиндексированы числами от

до

, столбцы -- парами таких чисел (числа в каждой паре разные). В клетке
![$[i, (j,k)]$ $[i, (j,k)]$](https://dxdy-02.korotkov.co.uk/f/1/b/9/1b9c1547bf09f6e5cfaa0b326ad751ae82.png)
стоит одно из чисел

(матрица, таким образом, задана неоднозначно), причём если

, то в клетке стоит обязательно

, а если

, то в клетке стоит обязательно

. Одноцветным прямоугольником относительно этой матрицы называется такая её подматрица, в которой во всех клетках стоит одно и то же число.
Доказать, что для любой такой матрицы кол-во одноцветных прямоугольников, необходимых для покрытия всей матрицы, не меньше

для некоторой константы

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