У Пети есть доска 40х40, клетки которой раскрашены в шахматном порядке, и много бумажных полосок, состоящих из пяти клеток того же размера, что и клетки доски. Каким наименьшим количеством полосок Петя сможет накрыть все черные клетки доски (полоски могут перекрываться и вылезать за край доски)?

задан 23 Мар '14 3:22

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

Рассмотрим такой план, когда в каждой строке 6 полосок покрывают по 3 чёрных клетки каждая. Это позволяет покрыть все чёрные клетки прямоугольника $%40\times36$%, используя 240 полосок. Остаётся прямоугольник $%40\times4$%, который по тому же принципу начинаем покрывать по столбцам. Тратя по 6 полосок на каждую из четырёх вертикалей, мы оставляем непокрытыми чёрные клетки квадрата $%4\times4$%. Их можно покрыть 4 полосками, и общее количество полосок составит $%240+24+4=268$%.

Покажем, что меньшим числом не обойтись. Для этого выделим некоторое количество чёрных клеток таким образом, что никакая полоска не может покрыть более одной выделенной клетки. Берём чёрную диагональ с 40 клетками. Параллельно ей идут две чёрные диагонали из 34 клеток; далее -- диагонали из 28 клеток, и так далее до диагоналей из 4 клеток. При этом расстояние между ближайшими выделенными клетками в строке или столбце составляет 6, и их одной полоской не накрыть. Всего при этом выделено $%2\cdot(4+10+16+22+28+34)+40=268$% клеток. Значит, это количество будет наименьшим возможным.

ссылка

отвечен 23 Мар '14 3:55

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

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

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

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

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

отмечен:

×3,931

задан
23 Мар '14 3:22

показан
1325 раз

обновлен
23 Мар '14 3:55

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

по почте:

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

по RSS:

Ответы

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

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