Разделы 
Дополнительно
Задача по математике - 1735
2019-01-20 
Даны $N \geq 3$ точек, занумерованных числами $1,2,\cdots, N$. Каждые две точки соединены стрелкой от меньшего к большему. Раскраску всех стрелок в красный и синий цвета назовем однотонной, если нет двух таких точек $A$ и $B$, что от $A$ до $B$ можно добраться и только по красным стрелкам, и только по синим. Найдите количество однотонных раскрасок.
Решение:
Назовем полный ориентированный граф на $N$ вершинах транзитивным, если его вершины можно занумеровать числами $1, 2, \cdots, N$ так, что любое ребро идет от вершины с меньшим номером к вершине с большим.
Лемма 1. Полный ориентированный граф транзитивен тогда и только тогда, когда любой его подграф на трех вершинах транзитивен.
Доказательство. Очевидно, что если граф транзитивен, то таковы же все его подграфы. Докажем обратное.
Индукция по $N$. База для $N = 3$ тривиальна. Пусть $N > 3$. Достаточно доказать, что существует вершина, из которой не ведет ни одного ребра. Тогда ее можно обозначить цифрой $N$ и применить к оставшимся вершинам предположение индукции.
Пусть такой вершины нет. Тогда из любой вершины выходит ребро. Выйдем из любой вершины по ребру, выходящему из нее, из той вершины, в которую мы попадем - снова по выходящему ребру и т. д. Когда-нибудь мы попадем в вершину, в которой уже побывали. Следовательно, в графе нашелся ориентированный цикл (скажем, $A_1A_2 .. .A_kA_1$). Так как треугольники $A_{k-1}A_kA_1, A_{k-2}A_{k-1}A_1,\cdots, A_3A_4A_1$ транзитивны, последовательно получаем, что ребра $A_{k-1}A_1, A_{k-2}A_1, \cdots, A_3A_1$ направлены к $A_1$. Но тогда треугольник $A_1A_2A_3$ нетранзитивен - противоречие.
Лемма 2. Пусть исходный граф покрашен в два цвета. Изменим все направления красных стрелок на противоположные. Раскраска однотонна тогда и только тогда, когда полученный граф также транзитивен.
Доказательство. Пусть раскраска однотонна. Достаточно доказать, что в полученном графе любой подграф на трех вершинах транзитивен. Действительно, пусть вершины $A < B < C$ образуют нетранзитивный треугольник. Тогда ребра идут либо $A \rightarrow B \rightarrow C \rightarrow A$, либо $A \rightarrow C \rightarrow B \rightarrow A$. Но в обоих случаях путь $ABC$ одноцветен и имеет другой цвет, нежели ребро $AC$, что невозможно.
Пусть, наоборот, полученный граф транзитивен. Если раскраска не была однотонной, то существуют одноцветные пути $A \rightarrow C_1 \rightarrow \cdots \rightarrow C_k \rightarrow B$ (красный) и $A \rightarrow D_1 \rightarrow \cdots \rightarrow D_l \rightarrow B$ (синий). Тогда в транзитивном графе нашелся ориентированный цикл $AD_1\cdots D_lBC_k \cdots C_1A$, что невозможно.
Теперь легко получить решение задачи. Действительно, однотонных раскрасок столько же, сколько возможно транзитивных графов на $N$ вершинах; их, в свою очередь, столько же, сколько перенумераций $N$ вершин, т. е. $N!$.
Ответ. $N!(N! = 1 \cdot 2 \cdot\cdots \cdot N)$.
Даны $N \geq 3$ точек, занумерованных числами $1,2,\cdots, N$. Каждые две точки соединены стрелкой от меньшего к большему. Раскраску всех стрелок в красный и синий цвета назовем однотонной, если нет двух таких точек $A$ и $B$, что от $A$ до $B$ можно добраться и только по красным стрелкам, и только по синим. Найдите количество однотонных раскрасок.
Решение:
Назовем полный ориентированный граф на $N$ вершинах транзитивным, если его вершины можно занумеровать числами $1, 2, \cdots, N$ так, что любое ребро идет от вершины с меньшим номером к вершине с большим.
Лемма 1. Полный ориентированный граф транзитивен тогда и только тогда, когда любой его подграф на трех вершинах транзитивен.
Доказательство. Очевидно, что если граф транзитивен, то таковы же все его подграфы. Докажем обратное.
Индукция по $N$. База для $N = 3$ тривиальна. Пусть $N > 3$. Достаточно доказать, что существует вершина, из которой не ведет ни одного ребра. Тогда ее можно обозначить цифрой $N$ и применить к оставшимся вершинам предположение индукции.
Пусть такой вершины нет. Тогда из любой вершины выходит ребро. Выйдем из любой вершины по ребру, выходящему из нее, из той вершины, в которую мы попадем - снова по выходящему ребру и т. д. Когда-нибудь мы попадем в вершину, в которой уже побывали. Следовательно, в графе нашелся ориентированный цикл (скажем, $A_1A_2 .. .A_kA_1$). Так как треугольники $A_{k-1}A_kA_1, A_{k-2}A_{k-1}A_1,\cdots, A_3A_4A_1$ транзитивны, последовательно получаем, что ребра $A_{k-1}A_1, A_{k-2}A_1, \cdots, A_3A_1$ направлены к $A_1$. Но тогда треугольник $A_1A_2A_3$ нетранзитивен - противоречие.
Лемма 2. Пусть исходный граф покрашен в два цвета. Изменим все направления красных стрелок на противоположные. Раскраска однотонна тогда и только тогда, когда полученный граф также транзитивен.
Доказательство. Пусть раскраска однотонна. Достаточно доказать, что в полученном графе любой подграф на трех вершинах транзитивен. Действительно, пусть вершины $A < B < C$ образуют нетранзитивный треугольник. Тогда ребра идут либо $A \rightarrow B \rightarrow C \rightarrow A$, либо $A \rightarrow C \rightarrow B \rightarrow A$. Но в обоих случаях путь $ABC$ одноцветен и имеет другой цвет, нежели ребро $AC$, что невозможно.
Пусть, наоборот, полученный граф транзитивен. Если раскраска не была однотонной, то существуют одноцветные пути $A \rightarrow C_1 \rightarrow \cdots \rightarrow C_k \rightarrow B$ (красный) и $A \rightarrow D_1 \rightarrow \cdots \rightarrow D_l \rightarrow B$ (синий). Тогда в транзитивном графе нашелся ориентированный цикл $AD_1\cdots D_lBC_k \cdots C_1A$, что невозможно.
Теперь легко получить решение задачи. Действительно, однотонных раскрасок столько же, сколько возможно транзитивных графов на $N$ вершинах; их, в свою очередь, столько же, сколько перенумераций $N$ вершин, т. е. $N!$.
Ответ. $N!(N! = 1 \cdot 2 \cdot\cdots \cdot N)$.
