Олимпиадная задача по комбинаторике и графам: однотонные раскраски стрелок между точками
Задача
Даны N≥ 3 точек, занумерованных числами 1, 2, ...,N. Каждые две точки соединены стрелкой от меньшего номера к большему. Раскраску всех стрелок в красный и синий цвета назовемоднотонной, если нет двух таких точекAиB, что отAдоBможно добраться и по красным стрелкам, и по синим. Найдите количество однотонных раскрасок.
Решение
Назовём полный ориентированный граф упорядоченным, если ориентированные ребра задают на множестве его вершин отношение (линейного) порядка. Граф из условия упорядоченнный.
Пусть исходный граф покрашен в два цвета. Изменим все направления красных стрелок на противоположные. Докажем, что раскраска однотонна тогда и только тогда, когда полученный граф – упорядоченный.
1) Пусть раскраска однотонна. Достаточно проверить в новом графе свойство транзитивности порядка. Пусть вершины A, B, C с номерами a < b < c образуют нетранзитивный треугольник: рёбра идут либо от A к B, от B к C, от C к A, либо от A к C, от C к B, от B к A. В обоих случаях в исходном графе путь ABC одноцветен и имеет другой цвет, нежели ребро AC. Противоречие.
2) Пусть полученный граф – упорядоченный. Рассмотрим две вершины A и B. Если в исходном графе от A к B вёл синий путь, то в новом графе A < B, а если красный, то A > B (в смысле нового порядка). Одновременно эти неравенства выполняться не могут.
Теперь легко получить ответ: однотонных раскрасок столько же, сколько отношений порядка на множестве из N элементов; их, в свою очередь, столько же, сколько перестановок N элементов, то есть N!.
Ответ
N!.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь