Раскраски в комбинаторных задачах
Метод раскраски позволяет доказывать невозможность замощения фигур или прохождения путей. Суть метода заключается в том, чтобы раскрасить элементы задачи (клетки доски, вершины графа) в несколько цветов и найти противоречие в количестве цветов.
Самая известная раскраска — шахматная (в 2 цвета). Она помогает решать задачи о покрытии доминошками (каждая доминошка всегда покрывает 1 черную и 1 белую клетку). Если из доски вырезали две белые клетки, замостить ее доминошками нельзя.
Существуют раскраски в 3, 4 цвета, раскраски полосками и диагоналями. Для задач с фигурами "уголок" (тримино) полезна раскраска в 4 цвета по квадратам 2x2. Выбор правильной раскраски — это искусство, требующее опыта.
Раскраски применяются и в пространственных задачах (с кубиками), и в теории графов (хроматическое число графа). Знаменитая проблема четырех красок утверждает, что любую плоскую карту можно раскрасить в 4 цвета так, чтобы соседние страны были разного цвета.
