Вот здесь я уже объявлял конкурс на решение своей задачки. Сейчас (в связи с появлением у меня более ценных призов, чем рука и сердце) я решил немного изменить условия конкурса (но не задачи). Итак, задачка.

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

Решить задачу означает найти формулу для зависимости Q(N) - максимально возможного числа закрашенных ячеек Q от стороны квадрата N. То есть надо доказать, что для каждого натурального N Q(N) ячеек можно закрасить так, чтобы выполнялось условие задачи, а Q(N)+1 - уже нельзя.

Объявляется конкурс до 31 декабря 2004 года включительно на решение данной задачи. Победителем конкурса будет объявлен тот, кто первым сумеет решить задачу и объяснить мне её решение. Победителя ждёт ценный приз - плитка шоколада Lindt 99%.