|
У Пети есть доска 40х40, клетки которой раскрашены в шахматном порядке, и много бумажных полосок, состоящих из пяти клеток того же размера, что и клетки доски. Каким наименьшим количеством полосок Петя сможет накрыть все черные клетки доски (полоски могут перекрываться и вылезать за край доски)? задан 23 Мар '14 3:22 
serg55 |
|
Рассмотрим такой план, когда в каждой строке 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 
falcao |