Условие
Даны
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!.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
2005 |
|
Этап |
|
Вариант |
4 |
|
|
1 |
|
Класс |
|
Класс |
10 |
|
задача |
|
Номер |
05.4.10.4 |
|
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
2005 |
|
Этап |
|
Вариант |
4 |
|
|
1 |
|
Класс |
|
Класс |
11 |
|
задача |
|
Номер |
05.4.11.3 |
