В задаче на разрезание предлагалось наименьшим числом прямых разрезов разделить квадрат $%5\times 5$% на клеточки (можно перекладывать полученные части). Ясно, что за 5 разрезов можно получить не более $%2^5=32$% кусочка. Однако для квадрата необходимо минимум 6 разрезов.

Обозначим через $%\lceil x\rceil$% наименьшее целое число, не меньшее x (округление вверх). Тогда для разрезания на k кусков нужно не менее $%N(k)=\lceil \log_2k\rceil$% разрезов. В частности, сторону длиной 5 можно разрезать на единичные отрезки не менее, чем за $%N(5)=3$% разреза.

Выдвигаются две гипотезы (ср. с ответом @onesickbastard).

  1. Можно ли считать, что в линейном случае (для отрезка длиной k) минимальное число разрезов равно именно $%N(k)$%?
  2. Можно ли доказать, что для прямоугольника $%m\times n$% минимальное число разрезов равно $%N(m)+N(n)$%?

задан 10 Апр '12 0:04

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

Введем функцию $%P(m,n)$% - минимальное кол-во разрезов прямоугольника размером $%m$%x$%n$% на единичные квадратики.
Очевидно, что если на некотором шаге разрезания у нас есть куча квадратиков $%m_i$%x$%n_i$%, то всего нам понадобится $%\max{P(m_i,n_i)}$% разрезаний, т.е. нас всегда будет интересовать самая "трудная" фигура.
Также понятно, что $%P(k,n)\geq P(m,n)$% при $%k>m$%.
Допустим, на некотором шаге мы разрезаем прямоугольник $%m$%x$%n$% на два: $%k$%x$%n$% и $%(m-k)$%x$%n$%. Тогда $%P(m,n)=\max(P(k,n),P(m-k,n))=P(\max(k,m-k),n)$%. Устремляя к минимуму $%\max(k,m-k)$%, получаем $%k=[\frac{m}{2}]$%.
$%P(m,n)=P(n,m)$%, следовательно, нас не интересует порядок разрезания по вертикали и горизонтали.
Из вышесказанного можно сделать вывод, что самый эффективный способ разрезания прямоугольника - на равные или практически равные части. А этот способ дает ровно $%N(m)+N(n)$% разрезаний, ч.т.д.
Применительно к первому вопросу: $%P(k)=P(k,1)=N(k)+N(1)=N(k)$%.

ссылка

отвечен 29 Сен '12 22:56

изменен 29 Сен '12 22:58

Высказывание "самый эффективный способ разрезания прямоугольника - на равные или практически равные части" в общем-то интуитивно понятно. Но у Вас оно не доказано, тем более, что слова "практически равные части" не имеют строгого математического смысла.

И почему этот способ дает N(m) + N(n) разрезов?

(29 Сен '12 23:52) DocentI

Извините, попробую расписать более формально.
Изо всех прямоугольников, получившихся после i-го разрезания, для нас всегда важен только прямоугольник наибольшей "сложности", про остальные можно забыть. Для первом шаге таковым является наибольший из двух прямоугольников, т.к. одна из сторон зафиксирована. Для наименьшего кол-ва разрезаний надо резать на "почти равные части" - новые стороны должны отличаться не более чем на 1. На следующем шаге забываем про меньший прямоугольник и повторяем алгоритм для большего. Таким образом, нам понадобится N(m) разрезаний по гор-ли и N(n) по верт-ли.

(30 Сен '12 0:49) chameleon

Ладно, вроде верно. Ключевой момент - минимизация максимума.

(30 Сен '12 1:15) DocentI
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,034
×38

задан
10 Апр '12 0:04

показан
1305 раз

обновлен
30 Сен '12 1:15

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

по почте:

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

по RSS:

Ответы

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

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