Разделы 
Дополнительно
Задача по математике - 1760
2019-01-20 
Назовем раскраску доски $8 \times 8$ в три цвета хорошей, если в любом уголке из пяти клеток присутствуют клетки всех трех цветов. (Уголок из пяти клеток - это фигура, получающаяся из квадрата $3 \times 3$ вырезанием квадрата $2 \times 2$). Докажите, что количество хороших раскрасок не меньше, чем $6^8$.
Решение:
Заметим, что любой уголок содержит горизонтальный прямоугольник $1 \times 3$. Также заметим, что любую горизонталь можно покрасить в три цвета так, чтобы любой прямоугольник $1 \times 3$ содержал клетки трех различных цветов, ровно $3! = 6$ способами (получится раскраска $ABCABCAB$, а цвета $ABC$ можно выбрать 6 способами). Это означает, что раскраска, при которой каждая горизонталь покрашена указанным способом, будет хорошей. Поскольку каждую горизонталь можно покрасить независимо от других, число хороших раскрасок такого вида будет в точности $6^8$.
Замечание. Покажем, что есть еще хорошие раскраски, которые мы не посчитали, например такая, при которой каждая из горизонталей одноцветна, а цвета горизонталей чередуются указанным выше образом (в этом случае любой вертикальный прямоугольник $1 \times 3$ будет содержать клетки трех различных цветов). Поэтому общее количество хороших раскрасок больше $6^8$.
Назовем раскраску доски $8 \times 8$ в три цвета хорошей, если в любом уголке из пяти клеток присутствуют клетки всех трех цветов. (Уголок из пяти клеток - это фигура, получающаяся из квадрата $3 \times 3$ вырезанием квадрата $2 \times 2$). Докажите, что количество хороших раскрасок не меньше, чем $6^8$.
Решение:
Заметим, что любой уголок содержит горизонтальный прямоугольник $1 \times 3$. Также заметим, что любую горизонталь можно покрасить в три цвета так, чтобы любой прямоугольник $1 \times 3$ содержал клетки трех различных цветов, ровно $3! = 6$ способами (получится раскраска $ABCABCAB$, а цвета $ABC$ можно выбрать 6 способами). Это означает, что раскраска, при которой каждая горизонталь покрашена указанным способом, будет хорошей. Поскольку каждую горизонталь можно покрасить независимо от других, число хороших раскрасок такого вида будет в точности $6^8$.
Замечание. Покажем, что есть еще хорошие раскраски, которые мы не посчитали, например такая, при которой каждая из горизонталей одноцветна, а цвета горизонталей чередуются указанным выше образом (в этом случае любой вертикальный прямоугольник $1 \times 3$ будет содержать клетки трех различных цветов). Поэтому общее количество хороших раскрасок больше $6^8$.
