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

задан 9 Янв '12 21:31

изменен 9 Янв '12 23:44

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

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

Не знаю, как доказать, что лучше способа нет (а может и есть), но у меня вышло 6 разрезов.
Исходил из того, что чем больше разрезанные части будут похожи друг на друга, тем лучше.
Пусть наш квадрат имеет координаты противоположных вершин (0, 0) и (5, 5) (чтоб удобнее задавать разрезы). Тогда первый разрез по прямой х=3. Правую часть двигаем к оси Оу (если нельзя накладывать друг на друга части, то двигаем ещё на 5 вверх. И делаем 2 разреза: по х=1 и х=2. Получилось 5 прямоугольников размера 1х5. Накладываем их один на один (или друг над другом, если нельзя накладывать: на результат наложение не влияет), и получившийся прямоугольник пусть имеет координаты (0, 0) и (5, 1). Повторяем аналогичную процедуру - ещё 3 разреза. Итого: 6.
Такой подход предполагает, что любой отрезок длины n можно разбить на единичные за [log2(n)] разрезаний => любой прямоугольник - за [log2(n)]+[log2(m)] разрезаний.
Будет интересно узнать решение получше.

ссылка

отвечен 12 Фев '12 23:47

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

Не очень понятно, что такое "прямоугольные" разрезы? Может, все-таки, прямолинейные?
Будем решать задачу именно в этом предположении. Обозначим через N(k) минимальное число разрезов, необходимое, чтобы разрезать фигуру на k частей. Ясно, что $%2^{N(k)} \geq k$%, так как за одно разрезание каждую прежнюю часть делим не более, чем на 2. В частности, $%N(25)\geq 5$%.

Пусть мы на каком-то шаге имеем максимальную неразрезанную часть в k квадратиков. Даже если мы наложим все остальные части на нее, нам будет нужно еще не менее N(k) разрезов.

Первым шагом мы можем разрезать квадрат на 5 + 20 квадратов. Тогда нужно еще не менее $%N(20)\geq 5$% разрезаний. Всего - не менее 6.
Если первый разрез на 10 + 15 квадратиков, нужно разрезать еще прямоугольник $%3\times 5$%. Для второго разреза возможны варианты: 3 + 12 = 6 + 9 = 5 + 10, что дает не менее $%2 + N(9)\geq 2 + 4 = 6$% разрезов. Итак, пример, найденный @onesickbastard, является оптимальным.

ссылка

отвечен 25 Мар '12 18:12

изменен 25 Мар '12 18:13

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

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

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

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

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

отмечен:

×2,325
×792
×790

задан
9 Янв '12 21:31

показан
3114 раз

обновлен
25 Мар '12 18:13

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

по почте:

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

по RSS:

Ответы

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

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