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