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