16-01-2004 23:02 Задачка.
Что-то меня на задачки потянуло...
Значится, так...
Имеется квадрат ("шахматная доска") размером NxN. Какое наибольшее число полей этой доски можно закрасить чёрным цветом так, чтобы выполнялось следующее условие.
Никакие 4 чёрных поля не могут образовывать прямоугольник (точнее, являться вершинами прямоугольника) со сторонами, параллельными сторонам квадрата.
Говоря шахматным языком, если поля c3, e3 и c7 закрашены чёрным цветом, то поле e7 закрашивать уже нельзя.
Это упрощённый вариант задачки, которую я поставил перед собой ещё в школе. Потом в бумажном дневнике пытался решать, но без особого успеха. Получил только верхние и нижние границы. А задачка заключалась в том, каким минимальным числом цветов можно раскрасить квадрат NxN, чтобы для каждого цвета выполнялось указанное условие. Я тогда получил некоторые частные результаты, например, показал, что 10 - максимальная сторона квадрата, который можно раскрасить тремя цветами. И даже получил соответствующую раскраску. Всё руками, компьютера тогда не было, конечно.
Значится, так...
Имеется квадрат ("шахматная доска") размером NxN. Какое наибольшее число полей этой доски можно закрасить чёрным цветом так, чтобы выполнялось следующее условие.
Никакие 4 чёрных поля не могут образовывать прямоугольник (точнее, являться вершинами прямоугольника) со сторонами, параллельными сторонам квадрата.
Говоря шахматным языком, если поля c3, e3 и c7 закрашены чёрным цветом, то поле e7 закрашивать уже нельзя.
Это упрощённый вариант задачки, которую я поставил перед собой ещё в школе. Потом в бумажном дневнике пытался решать, но без особого успеха. Получил только верхние и нижние границы. А задачка заключалась в том, каким минимальным числом цветов можно раскрасить квадрат NxN, чтобы для каждого цвета выполнялось указанное условие. Я тогда получил некоторые частные результаты, например, показал, что 10 - максимальная сторона квадрата, который можно раскрасить тремя цветами. И даже получил соответствующую раскраску. Всё руками, компьютера тогда не было, конечно.
Комментарии:
Камрад
3(N-1) всегда можно закрасить. Если покрасить 2(N-1) так, чтобы они были единственными каждая в строке и столбце, и потом можно добавить еще (N-1). Но кажется, это не максимум?
Этих чисел я не понял. Но вообще я могу восстановить верхнюю границу. Напишу завтра утром. Я сильно подозреваю, что она является точным результатом, но конструктивного доказательства дать не могу.
Итак, верхняя граница.
Число закрашенных квадратов не может превышать
[N(k+1)/2 + N(N-1)/(2k)],
где
k=[sqrt(N-3/4) + 1/2].
В общем, верхняя граница имеет порядок N^(3/2).
Правда, эта формула всё равно не является точным решением, но по крайней мере она вроде близка к нему.
Число закрашенных квадратов не может превышать
[N(k+1)/2 + N(N-1)/(2k)],
где
k=[sqrt(N-3/4) + 1/2].
В общем, верхняя граница имеет порядок N^(3/2).
Правда, эта формула всё равно не является точным решением, но по крайней мере она вроде близка к нему.
отредактировано: 18-01-2004 08:29 - kv75
Камрад
Интересно, как ты считал. Как условный максимум?
Кажется, что самое доступное - по столбцам считать. Я не посчитала, потом буду пробовать. Рекуррентности тут ведь нет?
Кажется, что самое доступное - по столбцам считать. Я не посчитала, потом буду пробовать. Рекуррентности тут ведь нет?
Нет, рекуррентности в моём методе нет. Я потом ещё напишу про отклонения от этой формулы. Когда просчитаю точные результаты до N=13.
А методику не хочу сейчас говорить, чтобы не навязывать другим своего пути решения. Тем более что это и не решение, а только неплохая верхняя граница.
А методику не хочу сейчас говорить, чтобы не навязывать другим своего пути решения. Тем более что это и не решение, а только неплохая верхняя граница.
Я жив
[Print]
kv75