|
|
 |
Условие
Рассматривается доска 8×8, клетки которой пока не окрашены. Сколькими способами можно раскрасить доску в чёрный и белый цвета так, чтобы чёрных клеток было 31 и никакие две чёрные клетки не имели общей стороны? (Два способа раскраски считаются различными, если найдётся клетка, которая при одном из этих способах раскраски белая, а при другом – чёрная.)
Решение
Разобьём доску на 16 квадратиков 2×2. Ясно, что один из квадратиков – особый, в нем только одна чёрная клетка, а в остальных пятнадцати – по две, причём в противоположных углах. Раскраска неособого квадратика однозначно продолжается на соседний (по стороне) неособый квадратик и, тем самым, на все неособые квадратики. Без особого квадратика получается шахматная (или противоположная ей по раскраске) доска с дыркой. Если дырка находится в левом верхнем (см. рис.) или правом нижнем углу шахматной доски, то закрасить в ней одну клетку чёрным можно тремя способами, а в остальных случаях – только двумя. Итак, из шахматной доски можно получить 16·2 + 2 = 34 раскраски, а из противоположной ей – столько же.
Ответ
68 способами.
Замечания
4 балла
