Разделы 
Дополнительно
Задача по математике - 10401
2023-02-17 
Каждый из участников турнира встретился по одному разу со всеми остальными участниками, причем ни одна встреча не закончилась вничью. Доказать, что среди спортсменов найдется такой, кто назовет всех остальных участников турнира, если станет перечислять тех, кого победил он сам, и тех, кого победили побежденные им соперники.
Решение:
Первое решение. Пусть $A$ - участник турнира, выигравший наибольшее число встреч. Если бы утверждение задачи не выполнялось для $A$, то нашелся бы такой участник турнира $B$, над которым не удалось одержать победу ни самому $A$, ни побежденным им участникам турнира. Следовательно, $B$ одержал бы больше побед, чем $A$, что невозможно, поскольку $A$ по условию одержал наибольшее число побед. Таким образом, утверждение задачи выполняется для $A$.
Второе решение. Докажем утверждение задачи методом полной математической индукции. Если в турнире участвовали лишь два спортсмена, то утверждение задачи заведомо выполняется. Предположим, что оно верно в том случае, если число участников турнира равно $n$. Если число участников возрастет до $n + 1$, то по предположению индукции среди первых $n$ участников найдется такой спортсмен $A$, который, перечисляя всех, кого победил он сам и кого победили побежденные им соперники, назовет $n$ первых участников. Пусть $B$ последний из $n + 1$ участников турнира. Если спортсмен $A$, перечисляя тех участников турнира, кого победил он сам или побежденные им соперники, назовет спортсмена $B$, то для $A$ будет выполняться утверждение задачи. Если же $A$ не назовет $B$, то это будет означать, что $B$ одержал победу над $A$ и всеми, кого назвал $A$. В этом случае утверждение задачи выполняется для $B$.
Третье решение. Предложим всем участникам турнира собраться в зале. Пусть один из спортсменов выведет из зала тех, над кем ему удалось одержать победу (возможно, что выбранному нами спортсмену выводить из зала будет некого). Если после этого в зале еще останутся участники турнира, то попросим одного из них
вывести из зала тех, кого ему удалось победить. Так будем продолжать до тех пор, пока кто-нибудь не выведет из зала последних участников турнира. Тот, кто это сделает, победил всех спортсменов, которых он сам вывел из зала, и всех участников турнира, которые выводили из зала других спортсменов, но сами могли оставаться в зале. Оставшиеся в зале были победителями выведенных из зала спортсменов, поэтому участник турнира, который вывел из зала последних спортсменов, назвал всех участников турнира (кроме себя).
По поводу приведенных выше решений следует сделать несколько замечаний:
1. В первом решении показано, что для победителя турнира (или любого из победителей, если их оказалось несколько) утверждение задачи выполнено. Однако не следует думать, будто утверждение задачи выполняется лишь для победителей. Как показывает приводимая таблица, оно может выполняться даже для спортсмена, занявшего последнее место в турнире:
Более того, возможно, что утверждение задачи будет выполняться и для всех участников турнира. Примером может служить та же турнирная таблица.
2. Утверждение задачи можно сформулировать на языке теории графов. Сопоставим каждому участнику турнира по одной и только одной вершине графа. Вершины, соответствующие участникам каждой встречи, соединим ребром, направленным от одержавшего победу к проигравшему встречу. Исход турнира можно представить тогда в виде полного ориентированного графа, а утверждение задачи сформулировать так:
в любом конечном ориентированном полном графе найдется такая вершина, из которой, двигаясь по направлению, согласующемуся с ориентацией ребер, можно достичь любой другой вершины, если пройти одно или два смежных ребра.
Для бесконечных графов утверждение задачи неверно. Пусть, например, $P_{1}, P_{2}, P_{3}. \cdots $ - вершины бесконечного графа, а ребро $P_{i}P_{k}$ ориентировано от вершины с большим индексом к вершине с меньшим индексом. Тогда из любой вершины, двигаясь по направлению, указанному ориентацией ребер, можно достичь лишь вершин с меньшими значениями индексов, то есть попасть лишь в конечное число вершин.
Каждый из участников турнира встретился по одному разу со всеми остальными участниками, причем ни одна встреча не закончилась вничью. Доказать, что среди спортсменов найдется такой, кто назовет всех остальных участников турнира, если станет перечислять тех, кого победил он сам, и тех, кого победили побежденные им соперники.
Решение:
Первое решение. Пусть $A$ - участник турнира, выигравший наибольшее число встреч. Если бы утверждение задачи не выполнялось для $A$, то нашелся бы такой участник турнира $B$, над которым не удалось одержать победу ни самому $A$, ни побежденным им участникам турнира. Следовательно, $B$ одержал бы больше побед, чем $A$, что невозможно, поскольку $A$ по условию одержал наибольшее число побед. Таким образом, утверждение задачи выполняется для $A$.
Второе решение. Докажем утверждение задачи методом полной математической индукции. Если в турнире участвовали лишь два спортсмена, то утверждение задачи заведомо выполняется. Предположим, что оно верно в том случае, если число участников турнира равно $n$. Если число участников возрастет до $n + 1$, то по предположению индукции среди первых $n$ участников найдется такой спортсмен $A$, который, перечисляя всех, кого победил он сам и кого победили побежденные им соперники, назовет $n$ первых участников. Пусть $B$ последний из $n + 1$ участников турнира. Если спортсмен $A$, перечисляя тех участников турнира, кого победил он сам или побежденные им соперники, назовет спортсмена $B$, то для $A$ будет выполняться утверждение задачи. Если же $A$ не назовет $B$, то это будет означать, что $B$ одержал победу над $A$ и всеми, кого назвал $A$. В этом случае утверждение задачи выполняется для $B$.
Третье решение. Предложим всем участникам турнира собраться в зале. Пусть один из спортсменов выведет из зала тех, над кем ему удалось одержать победу (возможно, что выбранному нами спортсмену выводить из зала будет некого). Если после этого в зале еще останутся участники турнира, то попросим одного из них
вывести из зала тех, кого ему удалось победить. Так будем продолжать до тех пор, пока кто-нибудь не выведет из зала последних участников турнира. Тот, кто это сделает, победил всех спортсменов, которых он сам вывел из зала, и всех участников турнира, которые выводили из зала других спортсменов, но сами могли оставаться в зале. Оставшиеся в зале были победителями выведенных из зала спортсменов, поэтому участник турнира, который вывел из зала последних спортсменов, назвал всех участников турнира (кроме себя).
По поводу приведенных выше решений следует сделать несколько замечаний:
1. В первом решении показано, что для победителя турнира (или любого из победителей, если их оказалось несколько) утверждение задачи выполнено. Однако не следует думать, будто утверждение задачи выполняется лишь для победителей. Как показывает приводимая таблица, оно может выполняться даже для спортсмена, занявшего последнее место в турнире:
Более того, возможно, что утверждение задачи будет выполняться и для всех участников турнира. Примером может служить та же турнирная таблица.
2. Утверждение задачи можно сформулировать на языке теории графов. Сопоставим каждому участнику турнира по одной и только одной вершине графа. Вершины, соответствующие участникам каждой встречи, соединим ребром, направленным от одержавшего победу к проигравшему встречу. Исход турнира можно представить тогда в виде полного ориентированного графа, а утверждение задачи сформулировать так:
в любом конечном ориентированном полном графе найдется такая вершина, из которой, двигаясь по направлению, согласующемуся с ориентацией ребер, можно достичь любой другой вершины, если пройти одно или два смежных ребра.
Для бесконечных графов утверждение задачи неверно. Пусть, например, $P_{1}, P_{2}, P_{3}. \cdots $ - вершины бесконечного графа, а ребро $P_{i}P_{k}$ ориентировано от вершины с большим индексом к вершине с меньшим индексом. Тогда из любой вершины, двигаясь по направлению, указанному ориентацией ребер, можно достичь лишь вершин с меньшими значениями индексов, то есть попасть лишь в конечное число вершин.
