KV75.RU

О САЙТЕ
МАТЕМАТИКА
ИГРЫ
ИНТЕРНЕТ

Задача о раскраске квадрата

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

Никакие 4 чёрных поля не могут образовывать прямоугольник (точнее, являться вершинами прямоугольника) со сторонами, параллельными сторонам квадрата.

Говоря шахматным языком, если поля c3, e3 и c7 закрашены чёрным цветом, то поле e7 закрашивать уже нельзя.

 

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

Источник: 361775.