|
|
 |
Условие
Какое наименьшее количество цветов необходимо, чтобы покрасить все вершины, стороны и диагонали выпуклого n-угольника, если должны выполняться два условия:
1) каждые два отрезка, выходящие из одной вершины должны быть разного цвета;
2) цвет любой вершины должен отличаться от цвета любого отрезка, выходящего из неё?
Решение
Так как из каждой вершины выходит n – 1 отрезок и они все должны быть покрашены различными цветами, отличными от цвета этой вершины, то количество цветов должно быть не меньше чем n.
Докажем, что n цветов достаточно. Обозначим вершины через V0, V1, ..., Vn–1, цвета – числами 0, 1, ..., n – 1. Произведём раскраску следующим образом: отрезок ViVj
окрашивается цветом с номером i + j (mod n), а вершина Vi – цветом с номером 2i (mod n).
Несложно проверить, что такая окраска удовлетворяет условиям задачи.
Ответ
n цветов.
