Условие
Из доски 10×10 клеток удалили левую верхнюю и правую нижнюю клетки. Какое наибольшее число неперекрывающихся домино 1×2 можно разместить на оставшейся доске? Домино кладут по клеткам; оставлять клетки непокрытыми разрешено.
Подсказка
Шахматная раскраска даёт по 50 клеток каждого цвета. Удалённые углы одного цвета. Его осталось 48, а каждое домино покрывает одну клетку каждого цвета. Больше 48 домино невозможно.
В каждой из 8 средних строк кладём 5 горизонтальных домино. В верхней и нижней строках кладём по 4, оставляя по одной клетке.
Показать ответ
48
Пошаговое решение
- Получаем верхнюю границу раскраской
Шахматная раскраска даёт по 50 клеток каждого цвета. Удалённые углы одного цвета. Его осталось 48, а каждое домино покрывает одну клетку каждого цвета. Больше 48 домино невозможно.
- Строим размещение
В каждой из 8 средних строк кладём 5 горизонтальных домино. В верхней и нижней строках кладём по 4, оставляя по одной клетке.
- Проверяем достижимость границы
Получилось 8·5+2·4=48 домино. Раз верхняя граница достигнута, это максимум.
Ответ: 48