Квадрат разрезали на прямоугольники так, что любая прямая, параллельная одной из сторон квадрата и не содержащая сторон прямоугольников, пересекает ровно 30 прямоугольников. На какое наименьшее число прямоугольников мог быть разрезан квадрат?

Рассуждал как-то так: разобьем квадрат на четыре одинаковых квадрата вертикальной и горизонтальной прямой. Теперь левый верхний и правый нижний квадраты разрежем на 29 прямоугольников, проведя в них 28 вертикальных линий, а левый нижний и правый верхний квадраты разрежем на 29 прямоугольников горизонтальными линиями. Получится ровно 116 прямоугольников и, как легко понять, условия задачи выполняется.

Можете, пожалуйста, сказать: верно ли рассуждал?

задан 3 Янв '15 8:57

@volodya korolev: Вы построили пример на 116 прямоугольников. Для полного решения необходимо доказать, что менее, чем на 116 (или меньшее число) прямоугольников квадрат не может быть разрезан.

(3 Янв '15 12:26) EdwardTurJ
10|600 символов нужно символов осталось
1

Минимальность числа 116 можно доказать следующим образом. Рассмотрим 4 линии, пересекающие клетки, беря крайние горизонтали и вертикали. Каждая линия пересекает по 30 прямоугольников разбиения. Посмотрим на то, какими могут быть общие прямоугольники. Легко заметить, что никакой из прямоугольников, пересекаемый крайней левой вертикалью, не может быть пересекаем крайней правой вертикалью. Аналогично для горизонталей. Если некий прямоугольник пересекается и вертикалью, и горизонталью, то он непременно "угловой". Отсюда ясно, что имеется 4 "угловых" прямоугольника, и кроме них по 28 "своих" для каждой линий; итого 116.

ссылка

отвечен 3 Янв '15 14:23

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

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

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

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

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

отмечен:

×3,042

задан
3 Янв '15 8:57

показан
1407 раз

обновлен
4 Янв '15 15:04

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

по почте:

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

по RSS:

Ответы

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

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