Разделы 
Дополнительно
Задача по математике - 10414
2023-02-17 
Во время экскурсии выяснилось, что один из любых четырех ее участников встречался ранее с тремя остальными. Доказать, что среди любых четырех участников экскурсии всегда можно найти такого, который встречался ранее со всеми остальными экскурсантами.
Решение:
Задача относится лишь к тому случаю, когда число экскурсантов не меньше 4. Если число экскурсантов меньше 4, то условия задачи и ее утверждение утрачивают смысл.
Пусть $A$ и $B$ - два не встречавшихся ранее экскурсанта. Такое предположение допустимо, поскольку в противном случае каждый экскурсант встречался бы ранее со всеми остальными участниками экскурсии и утверждение задачи выполнялось бы для любого экскурсанта. Предположим также, что еще два экскурсанта, образующие пару, отличную от $AB$, впервые встречаются во время экскурсии, поскольку в противном случае среди любых четырех экскурсантов нашелся бы такой (и даже два таких), который встречался ранее со всеми остальными экскурсантами.
В состав пары экскурсантов, отличной от пары $AB$, но также не встречавшейся ранее, непременно должны входить либо $A$, либо $B$. Действительно, предположим, что в состав этой пары (обозначим ее $CD$) не входят ни $A$, ни $B$. Тогда среди четырех экскурсантов $A, B, C, D$ нельзя было бы найти ни одного, встречавшегося ранее с тремя остальными экскурсантами, а это противоречит условиям задачи. Итак, предположим, что пару не встречавшихся ранее экскурсантов, отличную от пары $AB$, образуют экскурсанты $AC$ (подходящим выбором обозначений мы всегда можем добиться этого).
Выясним теперь, можно ли найти среди пар экскурсантов, отличных от пар $AB$ и $AC$, такие, что входящие в них экскурсанты не встречались ранее. По доказанному выше в каждую такую пару должен входить либо $A$, либо $B$, но точно такие же рассуждения применимы и к паре $AC$. Следовательно, среди любых двух не встречавшихся ранее экскурсантов должны быть либо $A$, либо $C$. Таким образом, «новой» парой не встречавшихся ранее экскурсантов могут быть лишь $BC$ или $AD$, где $D$ - не упоминавшийся ранее экскурсант.
Но последний случай невозможен, поскольку четыре экскурсанта $A, B, C$ и $D$ не удовлетворяли бы условиям задачи. Следовательно, если не считать пар $AB, АС$, то впервые встретиться могли лишь экскурсанты, образующие пару $BC$. Следовательно, если не считать экскурсантов $A, B$ и $C$, то любой из остальных экскурсантов встречался ранее со всеми участниками экскурсии. Поскольку среди любых четырех экскурсантов всегда найдется один экскурсант, отличный от $A, B$ и $C$, то утверждение задачи доказано.
Задача допускает «перевод» на язык теории графов. Каждому экскурсанту поставим в соответствие одну и только одну вершину графа и соединим ребром те вершины, «владельцы» которых не встречались ранее. По условиям задачи мы получим конечный граф, все ребра которого соединяют по две различных вершины и каждая пара вершин соединена не более чем одним ребром. В этом решении, говоря о графах, мы всегда будем иметь в виду лишь такие графы.
Задачу, эквивалентную исходной, можно сформулировать следующим образом. Пусть среди вершин графа, число которых $\geq 4$, нельзя найти такие четыре, каждая из которых была бы соединена ребром по крайней мере с одной из трех остальных вершин. Тогда среди любых четырех вершин графа найдется такая, которая не соединена ребром ни с одной из остальных вершин.
На языке теории графов решение задачи получается короче и нагляднее. Приведенное выше первое решение выглядит так.
Не ограничивая общности, предположим, что у графа имеются по крайней мере два ребра $a$ и $b$, поскольку в противном случае из всех вершин, за исключением, быть может, двух, не выходило бы ни одного ребра и среди любых четырех вершин графа нашлась бы такая вершина, из которой не выходило бы ни одного ребра. Ребра $a$ и $b$ имеют один общий конец, поскольку в противном случае их концы образовали бы четверку точек, не удовлетворяющую условиям задачи. Рассуждая аналогично, установим, что, не считая самих ребер $a, b$, в графе может быть лишь одно ребро, притом имеющее по крайней мере один общий конец с ребрами $a$ и $b$. Это ребро либо соединяет свободные концы ребер $a$ и $b$, либо выходит из их общей вершины (рис.). Последний случай отпадает, поскольку существование вершины, из которой выходят 3 ребра, противоречит условиям задачи. Таким образом, ребрами могут быть соединены лишь три вершины графа, совпадающие с концами ребер $a$ и $b$. Тем самым доказано, что какие бы четыре вершины мы ни выбрали, среди них непременно найдется по крайней мере одна, не соединенная ребрами ни с какой другой вершиной графа.
Во время экскурсии выяснилось, что один из любых четырех ее участников встречался ранее с тремя остальными. Доказать, что среди любых четырех участников экскурсии всегда можно найти такого, который встречался ранее со всеми остальными экскурсантами.
Решение:
Задача относится лишь к тому случаю, когда число экскурсантов не меньше 4. Если число экскурсантов меньше 4, то условия задачи и ее утверждение утрачивают смысл.
Пусть $A$ и $B$ - два не встречавшихся ранее экскурсанта. Такое предположение допустимо, поскольку в противном случае каждый экскурсант встречался бы ранее со всеми остальными участниками экскурсии и утверждение задачи выполнялось бы для любого экскурсанта. Предположим также, что еще два экскурсанта, образующие пару, отличную от $AB$, впервые встречаются во время экскурсии, поскольку в противном случае среди любых четырех экскурсантов нашелся бы такой (и даже два таких), который встречался ранее со всеми остальными экскурсантами.
В состав пары экскурсантов, отличной от пары $AB$, но также не встречавшейся ранее, непременно должны входить либо $A$, либо $B$. Действительно, предположим, что в состав этой пары (обозначим ее $CD$) не входят ни $A$, ни $B$. Тогда среди четырех экскурсантов $A, B, C, D$ нельзя было бы найти ни одного, встречавшегося ранее с тремя остальными экскурсантами, а это противоречит условиям задачи. Итак, предположим, что пару не встречавшихся ранее экскурсантов, отличную от пары $AB$, образуют экскурсанты $AC$ (подходящим выбором обозначений мы всегда можем добиться этого).
Выясним теперь, можно ли найти среди пар экскурсантов, отличных от пар $AB$ и $AC$, такие, что входящие в них экскурсанты не встречались ранее. По доказанному выше в каждую такую пару должен входить либо $A$, либо $B$, но точно такие же рассуждения применимы и к паре $AC$. Следовательно, среди любых двух не встречавшихся ранее экскурсантов должны быть либо $A$, либо $C$. Таким образом, «новой» парой не встречавшихся ранее экскурсантов могут быть лишь $BC$ или $AD$, где $D$ - не упоминавшийся ранее экскурсант.
Но последний случай невозможен, поскольку четыре экскурсанта $A, B, C$ и $D$ не удовлетворяли бы условиям задачи. Следовательно, если не считать пар $AB, АС$, то впервые встретиться могли лишь экскурсанты, образующие пару $BC$. Следовательно, если не считать экскурсантов $A, B$ и $C$, то любой из остальных экскурсантов встречался ранее со всеми участниками экскурсии. Поскольку среди любых четырех экскурсантов всегда найдется один экскурсант, отличный от $A, B$ и $C$, то утверждение задачи доказано.
Задача допускает «перевод» на язык теории графов. Каждому экскурсанту поставим в соответствие одну и только одну вершину графа и соединим ребром те вершины, «владельцы» которых не встречались ранее. По условиям задачи мы получим конечный граф, все ребра которого соединяют по две различных вершины и каждая пара вершин соединена не более чем одним ребром. В этом решении, говоря о графах, мы всегда будем иметь в виду лишь такие графы.
Задачу, эквивалентную исходной, можно сформулировать следующим образом. Пусть среди вершин графа, число которых $\geq 4$, нельзя найти такие четыре, каждая из которых была бы соединена ребром по крайней мере с одной из трех остальных вершин. Тогда среди любых четырех вершин графа найдется такая, которая не соединена ребром ни с одной из остальных вершин.
На языке теории графов решение задачи получается короче и нагляднее. Приведенное выше первое решение выглядит так.
Не ограничивая общности, предположим, что у графа имеются по крайней мере два ребра $a$ и $b$, поскольку в противном случае из всех вершин, за исключением, быть может, двух, не выходило бы ни одного ребра и среди любых четырех вершин графа нашлась бы такая вершина, из которой не выходило бы ни одного ребра. Ребра $a$ и $b$ имеют один общий конец, поскольку в противном случае их концы образовали бы четверку точек, не удовлетворяющую условиям задачи. Рассуждая аналогично, установим, что, не считая самих ребер $a, b$, в графе может быть лишь одно ребро, притом имеющее по крайней мере один общий конец с ребрами $a$ и $b$. Это ребро либо соединяет свободные концы ребер $a$ и $b$, либо выходит из их общей вершины (рис.). Последний случай отпадает, поскольку существование вершины, из которой выходят 3 ребра, противоречит условиям задачи. Таким образом, ребрами могут быть соединены лишь три вершины графа, совпадающие с концами ребер $a$ и $b$. Тем самым доказано, что какие бы четыре вершины мы ни выбрали, среди них непременно найдется по крайней мере одна, не соединенная ребрами ни с какой другой вершиной графа.
