Если кому-то непросто, то можете просто добиться как можно более хорошей оценки👍 Для начала можно просто понять, почему на бесконечной клетчатой плоскости, покрашеной в N цветов, найдётся хотя бы одна монохроматическая подматрица k×k

Монохроматической подматрицей называется k² клеток таблицы, находящиеся на пересечении k строк и k столбцов, покрашенные в один цвет.

Дано натуральное k. Доказать, что существует C>0, такое что в любой квадратной клетчатой таблице со стороной CN^k, покрашенной в N цветов, найдется не менее N^{k²+1} монохроматических подматриц k×k. Монохроматической подматрицей называется k² клеток таблицы, находящиеся на пересечении k строк и k столбцов, покрашенные в один цвет.