Восемь лет спустя
kv75
дневник заведен 05-10-2003
постоянные читатели [82]
закладки:
цитатник:
дневник:
местожительство:
Москва
интересы [13]
шахматы, грибы, Пратчетт, Иваси, Morrowind, Guild Wars
[1] 08-05-2008 07:37
Альпы

[Print]
Элизабет
16-01-2004 23:02 Задачка.
Что-то меня на задачки потянуло...
Значится, так...

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

Это упрощённый вариант задачки, которую я поставил перед собой ещё в школе. Потом в бумажном дневнике пытался решать, но без особого успеха. Получил только верхние и нижние границы. А задачка заключалась в том, каким минимальным числом цветов можно раскрасить квадрат NxN, чтобы для каждого цвета выполнялось указанное условие. Я тогда получил некоторые частные результаты, например, показал, что 10 - максимальная сторона квадрата, который можно раскрасить тремя цветами. И даже получил соответствующую раскраску. Всё руками, компьютера тогда не было, конечно.
Комментарии:
17-01-2004 19:48
Камрад
3(N-1) всегда можно закрасить. Если покрасить 2(N-1) так, чтобы они были единственными каждая в строке и столбце, и потом можно добавить еще (N-1). Но кажется, это не максимум?
17-01-2004 21:37
грандмастер свалкограф
Этих чисел я не понял. Но вообще я могу восстановить верхнюю границу. Напишу завтра утром. Я сильно подозреваю, что она является точным результатом, но конструктивного доказательства дать не могу.
18-01-2004 08:15
грандмастер свалкограф
Итак, верхняя граница.
Число закрашенных квадратов не может превышать
[N(k+1)/2 + N(N-1)/(2k)],
где
k=[sqrt(N-3/4) + 1/2].
В общем, верхняя граница имеет порядок N^(3/2).
Правда, эта формула всё равно не является точным решением, но по крайней мере она вроде близка к нему.

отредактировано: 18-01-2004 08:29 - kv75

19-01-2004 12:13
Камрад
Интересно, как ты считал. Как условный максимум?
Кажется, что самое доступное - по столбцам считать. Я не посчитала, потом буду пробовать. Рекуррентности тут ведь нет?
19-01-2004 18:15
грандмастер свалкограф
Нет, рекуррентности в моём методе нет. Я потом ещё напишу про отклонения от этой формулы. Когда просчитаю точные результаты до N=13.
А методику не хочу сейчас говорить, чтобы не навязывать другим своего пути решения. Тем более что это и не решение, а только неплохая верхняя граница.

Ваш комментарий:
Камрад:
Гость [+]
Гость
OpenID
залогиниться
Логин/пароль
залогиниться
Комментарий:
  • B
  • I
  • U
  • S
  • Small
  • CUT
  • URL
  • IMG
  • V
  • #
  • List
  • List=
  • OT
  • maroon
  • green
  • blue
  • center
  • right
  • JU
  • J
  • QUOTE
  • HTML
  • TRANSLIT » RUS
Дополнительно:
Автоматическое распознавание URL
Не преобразовывать смайлики
Cкрыть комментарий