Что-то меня на задачки потянуло...
Значится, так...

Имеется квадрат ("шахматная доска") размером NxN. Какое наибольшее число полей этой доски можно закрасить чёрным цветом так, чтобы выполнялось следующее условие.
Никакие 4 чёрных поля не могут образовывать прямоугольник (точнее, являться вершинами прямоугольника) со сторонами, параллельными сторонам квадрата.
Говоря шахматным языком, если поля c3, e3 и c7 закрашены чёрным цветом, то поле e7 закрашивать уже нельзя.

Это упрощённый вариант задачки, которую я поставил перед собой ещё в школе. Потом в бумажном дневнике пытался решать, но без особого успеха. Получил только верхние и нижние границы. А задачка заключалась в том, каким минимальным числом цветов можно раскрасить квадрат NxN, чтобы для каждого цвета выполнялось указанное условие. Я тогда получил некоторые частные результаты, например, показал, что 10 - максимальная сторона квадрата, который можно раскрасить тремя цветами. И даже получил соответствующую раскраску. Всё руками, компьютера тогда не было, конечно.