Олимпиадная задача по комбинаторике и графам: однотонные раскраски стрелок между точками
Даны N≥ 3 точек, занумерованных числами 1, 2, ...,N. Каждые две точки соединены стрелкой от меньшего номера к большему. Раскраску всех стрелок в красный и синий цвета назовемоднотонной, если нет двух таких точекAиB, что отAдоBможно добраться и по красным стрелкам, и по синим. Найдите количество однотонных раскрасок.
Показать ответ
N!.
Разобрать решение
Назовём полный ориентированный граф упорядоченным, если ориентированные ребра задают на множестве его вершин отношение (линейного) порядка. Граф из условия упорядоченнный.
Пусть исходный граф покрашен в два цвета. Изменим все направления красных стрелок на противоположные. Докажем, что раскраска однотонна тогда и только тогда, когда полученный граф – упорядоченный.
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!.
Обсуждение
0Комментариев пока нет.