Разделы 
Дополнительно
Задача по математике - 3698
2019-06-15 
Дано $n$ точек, $n > 4$. Докажите, что можно соединить их стрелками так, чтобы из каждой точки в каждую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).
Решение:
Задача решается по индукции. Для $n = 3, n = 5$ и $n = 6$ требуемые системы точек изображены на рис. а-в, а на рис. г показан один из способов, позволяющих из системы $n$ точек $A_1, A_2, \cdots, A_n$, соединенных нужным образом стрелками, получить требуемую систему с $n + 2$ точками $A_1, A_2, \cdots, A_n, A_{n+1}, A_{n+2}$. Для этого к уже имеющимся стрелкам добавим стрелки, идущие из $A_{n+1}$ ко всем точкам $A_1, A_2, \cdots A_n$; из каждой точки $A_1, A_2, \cdots, A_n$, проведем стрелку в $A_{n+2}$; наконец, из $A_{n+2}$ - стрелку в точку $A_{n+1}$.
В силу принципа полной индукции утверждение задачи справедливо при всех нечетных $n \geq 3$ и всех четных $n \geq 6$.
Для $n = 4$ требуемой системы точек не существует.
Дано $n$ точек, $n > 4$. Докажите, что можно соединить их стрелками так, чтобы из каждой точки в каждую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).
Решение:
Задача решается по индукции. Для $n = 3, n = 5$ и $n = 6$ требуемые системы точек изображены на рис. а-в, а на рис. г показан один из способов, позволяющих из системы $n$ точек $A_1, A_2, \cdots, A_n$, соединенных нужным образом стрелками, получить требуемую систему с $n + 2$ точками $A_1, A_2, \cdots, A_n, A_{n+1}, A_{n+2}$. Для этого к уже имеющимся стрелкам добавим стрелки, идущие из $A_{n+1}$ ко всем точкам $A_1, A_2, \cdots A_n$; из каждой точки $A_1, A_2, \cdots, A_n$, проведем стрелку в $A_{n+2}$; наконец, из $A_{n+2}$ - стрелку в точку $A_{n+1}$.
В силу принципа полной индукции утверждение задачи справедливо при всех нечетных $n \geq 3$ и всех четных $n \geq 6$.
Для $n = 4$ требуемой системы точек не существует.
