В задаче на разрезание предлагалось наименьшим числом прямых разрезов разделить квадрат $%5\times 5$% на клеточки (можно перекладывать полученные части). Ясно, что за 5 разрезов можно получить не более $%2^5=32$% кусочка. Однако для квадрата необходимо минимум 6 разрезов. Обозначим через $%\lceil x\rceil$% наименьшее целое число, не меньшее x (округление вверх). Тогда для разрезания на k кусков нужно не менее $%N(k)=\lceil \log_2k\rceil$% разрезов. В частности, сторону длиной 5 можно разрезать на единичные отрезки не менее, чем за $%N(5)=3$% разреза. Выдвигаются две гипотезы (ср. с ответом @onesickbastard).
задан 10 Апр '12 0:04 DocentI |
Введем функцию $%P(m,n)$% - минимальное кол-во разрезов прямоугольника размером $%m$%x$%n$% на единичные квадратики. отвечен 29 Сен '12 22:56 chameleon Высказывание "самый эффективный способ разрезания прямоугольника - на равные или практически равные части" в общем-то интуитивно понятно. Но у Вас оно не доказано, тем более, что слова "практически равные части" не имеют строгого математического смысла. И почему этот способ дает N(m) + N(n) разрезов?
(29 Сен '12 23:52)
DocentI
Извините, попробую расписать более формально.
(30 Сен '12 0:49)
chameleon
Ладно, вроде верно. Ключевой момент - минимизация максимума.
(30 Сен '12 1:15)
DocentI
|