В таблице n*n закрасили n клеток. Найти наибольший периметр прямоугольника, не содержащего закрашенных клеток. который заведомо можно найти в таблице

задан 21 Янв '17 15:47

10|600 символов нужно символов осталось
1

Если раскрасить клетки по диагонали, то у любого прямоугольника без закрашенных клеток сумма длин сторон не превосходит n, и периметр не больше 2n. Покажем, что это значение оптимально, то есть его всегда можно достичь или превысить.

Пусть раскраска произвольна. Если есть пустая срока или столбец, то можно выбрать прямоугольник со сторонами 1 и n. Допустим, что в каждой строке и в каждом столбце есть закрашенная клетка, то есть пустых строк и столбцов нет. Тогда на каждой линии такая клетка ровно одна. Рассмотрим крайний справа столбец и его раскрашенную клетку. Тогда за ней имеется прямоугольник со сторонами 1 и n-1 без закрашенных клеток.

ссылка

отвечен 21 Янв '17 16:04

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,727
×99

задан
21 Янв '17 15:47

показан
439 раз

обновлен
21 Янв '17 16:23

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru