Раскраски

Сразу можно сказать, что цветов хотя бы , так как все клетки в нижней строке должны быть покрашены в разные цвета. Давайте покрасим первую строчку в цвета от 1 до по порядку. А каждую следующую строчку будем красить со сдвигом на 2. По вертикали и горизонтали клетки одного цвета друг друга бить не будут.

Нужно проверить, что клетка цвета в последней строке не окажется под боем клетки цвета в первой строке. Пусть — номер строки, больший 1, тогда клетка цвета в этой строке стоит в столбце. Значит, в последней строке клетка цвета стоит в столбце (1).

Теперь заметим, что если у цвета не было перехода через границу, то очевидно, что по диагонали клетки одного цвета друг друга не бьют. А если переход был, то между клеткой цвета в первой строке и в последней строке есть столбец (это следует из (1)), ну тогда и в этом случае по диагонали клетки одного цвета друг друга не бьют, значит, приведенная раскраска таблицы подходит.