геометрия - Разрезание квадрата

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

комбинаторика олимпиада геометрия

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

Оксана
24●3●6

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

ХэшКод
55●2●5

2 ответа

старые новые ценные

Не знаю, как доказать, что лучше способа нет (а может и есть), но у меня вышло 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

onesickbastard
109●1●7

Не очень понятно, что такое "прямоугольные" разрезы? Может, все-таки, прямолинейные?
Будем решать задачу именно в этом предположении. Обозначим через 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

DocentI
10.0k●4●21●52

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

Ваш ответ

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

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

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

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

регистрация »

отмечен:

геометрия ×3,293
комбинаторика ×1,650
олимпиада ×1,164

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

показан
5096 раз

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

Связанные исследования

Связанные вопросы

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

по почте:

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

по RSS:

Ответы

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