Турниры — Страница 2 — Задачи на Графы

На турнир приехал 101 человек. Известно, что среди любых 100 из них есть человек, знакомый со всеми остальными. Докажите, что найдется человек, который знаком со всеми остальными.

Подсказка

Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А.

Решение

Будем называть участников турнира игроками. Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А. Уберем игрока Б. Со всеми оставшимися может быть знаком только игрок A : иначе игрок $\mathrm{C} \neq \mathrm{A}$ , знакомый со всеми оставшимися, будет знаком и с Б, что противоречит нашему предположению. Назовем таких игроков А и Б антиподами. Из проведенного рассуждения следует, что при нашем предположении у каждого игрока А есть единственный антипод Б, для которого А в свою очередь является антиподом. Но это значит, что все игроки должны разбиться на пары антиподов, а это невозможно, ибо число игроков нечетно. Противоречие.

На турнир приехало 100 человек. Из любых пяти из них можно по крайней мере двумя способами выбрать трех попарно знакомых. Докажите, что среди них есть по крайней мере 4850 пар знакомых.

Подсказка

Решение

Рассмотрим граф, вершинами которого являются участники турнира, а ребрами — пары участников, незнакомых между собой. Если в этом графе есть треугольник $A B C$ , то в любой пятерке $A B C D E$ участники $D$ и $E$ должны быть знакомы между собой, и каждый из них должен быть знаком с двоими из тройки $A B C$ . Тогда пар знакомых получается не меньше, чем $97 \times 96 / 2+2 \times 97=97 \times 50=4850$ . Дальше будем считать, что треугольников нет. Пусть есть цикл $A B C D$ длины 4. Добавляя сюда произвольного участника $E$ , находим, что он дружит со всеми участниками из этого цикла, $A$ дружит с $C$ и $B$ дружить с $D$ . Таким образом, каждый цикл длины 4 в нашем графе является компонентой связности. Заметим далее, что в нашем графе нет незамкнутых путей длины 4: если есть такой путь $A B C D E$ , то в пятерке $A B C D E$ нет двух троек попарно знакомых. Поэтому нет и циклов длины больше 4 , то есть каждая компонента связности нашего графа — либо цикл длины 4, либо дерево. Но в такой ситуации ребер у этого графа не больше, чем вершин, то есть не больше 100. Соответственно, пар знакомых не меньше, чем $100 \times 99 / 2-100=4850$ .

Задача 090

Задача 095