|
|
 |
Условие
Назовём раскраску доски 8×8 в три цвета хорошей, если в любом уголке из пяти клеток присутствуют клетки всех трёх цветов. (Уголок из пяти клеток – это фигура, получающаяся из квадрата 3×3 вырезанием квадрата 2×2.) Докажите, что количество хороших раскрасок не меньше чем 68.
Решение
Каждый уголок содержит горизонтальный прямоугольник 1×3. Любую горизонталь можно покрасить в три цвета так, чтобы каждый прямоугольник 1×3 содержал клетки трёх различных цветов, ровно 6 способами (получится раскраска ABCABCAB, а цвета A, B, C можно выбрать 6 способами).
Это означает, что раскраска, при которой каждая горизонталь покрашена указанным способом, будет хорошей. Поскольку каждую горизонталь можно покрасить независимо от других, число хороших раскрасок такого вида будет в точности 68.
Но есть еще хорошие раскраски, которые мы не посчитали, например такая, при которой каждая из горизонталей одноцветна, а цвета горизонталей чередуются указанным выше образом (в этом случае любой вертикальный прямоугольник 1×3 будет содержать клетки трёх различных цветов). Поэтому общее количество хороших раскрасок больше 68.
