Question

РАСКРАСКА доски Дана клетчатая доска 6 x 8. Раскрась её клетки как можно меньшим количеством цветов так, чтобы для каждой клетки её противоположные соседи по стороне были разных цветов, а её противоположные соседи по диагонали - одного цвета (каждая клетка целиком красится в один ИЗ цветов). (Если у клетки для какого-то eë соседа нет противоположного (например, если клетка находится на краю доски), то считается, что для этого соседа условие выполнено.) Противоположные соседи по стороне Противоположные соседи по диагонали А) Сколько всего цветов понадобилось? Б) Попробуй доказать, что меньшим числом цветов обойтись нельзя.​

Answer 1

Ответ:><><><><

<><><><>

><><><><

<><><><>

><><><><

<><><><>

Пошаговое объяснение:

> - цвет 1

< - цвет 2

Answer 2

Для решения данной задачи можно использовать метод жадного алгоритма.

А) Для начала раскрасим первую клетку в любой цвет. Затем будем поочередно раскрашивать оставшиеся клетки доски, придерживаясь следующего правила: если соседняя клетка по стороне уже окрашена в определенный цвет, то текущую клетку окрашиваем в любой другой цвет, не совпадающий с цветом соседней клетки. Если соседняя клетка по диагонали уже окрашена, то текущую клетку окрашиваем в тот же цвет. Повторяем этот процесс до тех пор, пока не будут окрашены все клетки доски.

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

Теперь рассмотрим случай, когда как минимум одна клетка находится на краю доски. Если бы мы использовали только 2 цвета, то соседняя клетка по стороне для клетки на краю не имела бы противоположного соседа, что противоречит условию задачи. Следовательно, для данного случая также необходимо использовать минимум 3 цвета.

Таким образом, мы доказали, что меньшим числом цветов обойтись нельзя и в данной задаче необходимо использовать минимум 3 цвета.