Турниры — Задачи на Графы

Задача 008

01.01.2025 от

В чемпионате по футболу участвовало 72 команды. Каждые две команды встречались не более одного раза. Оказалось, что любые 48 команд провели между собой не менее 24 игр. Какое наименьшее количество игр могло состояться в этом чемпионате?

Подсказка

Рассмотрите вершину наибольшей степени. Удалите её из графа. Что можно сделать дальше?

Решение

Ответ: 72.

Решение: Обозначим команды точками, а матчи — соединяющими точки отрезками. Возьмем точку, из которой выходит больше всего отрезков, присвоим ей номер 1 и сотрем все исходящие из нее отрезки. После этого рассмотрим точку, из которой выходит больше всего оставшихся отрезков, присвоим ей номер 2, сотрем все исходящие из нее отрезки и т.д. Если из каждой из первых 24 точек перед стиранием выходило не меньше, чем по 2 отрезка, то всего отрезков не менее $2 \times 24+24=72$ , поскольку команды с номерами от 25 до 72 сыграли между собой не менее 24 матчей. Если же из точки 24 перед стиранием выходило не более 1 отрезка, то из точек от 25 до 72 в этот момент тоже выходит не более, чем по одному отрезку, и среди команд с номерами от 24 до 72 нетрудно найти 48 команд, сыгравшие менее 24 матчей. Итак, матчей сыграно не менее 72 . Пример на 72 матча: команды выстраиваются по кругу, и каждая играет со следующей по часовой стрелке. В самом деле, уберем 24 из этих 72 команд. Они уменьшили число сыгранных матчей максимум на $2 \times 24=48$ , поэтому оставшиеся 48 команд сыграли между собой не меньше 24 матчей.

Задача 009

01.01.2025 от

В день Св. Валентина $n$ влюбленных пар провели два однокруговых турнира по пинг-понгу — один для юношей, другой для девушек. Юноша и девушка из каждой пары вместе выиграли $n-1$ игру. Докажите, что количество троек юношей ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ , равно количеству таких троек девушек.

Подсказка

Попробуйте сравнить не количество циклических троек, а количество оставшихся троек.

Решение

Занумеруем все пары числами от 1 до $n$ . Пусть в паре с номером $k$ юноша выиграл $a_{k}$ , а девушка $-n-1-a_{k}$ партий. Заметим, что тогда девушка из этой пары проиграла $a_{k}$ партий.

Заметим, что общие количества троек юношей и девушек равны. Поэтому, чтобы сравнить количества троек юношей и девушек ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ (далее будем называть такие тройки циклическими) достаточно сравнить количества оставшихся (нециклических) троек. Заметим, что в каждой нециклической тройке есть ровно один человек, выигравший обе свои партии и ровно один человек, обе партии проигравший.

Рассмотрим теперь пару номер $k$ . Легко видеть, что количество троек юношей, в которых юноша из $k$ -й пары выиграл обе партии равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ . Поскольку в каждой нециклической тройке юношей есть ровно один юноша, одержавший две победы, количество таких троек равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ . Аналогично, количество троек девушек, в которых девушка из $k$ -й пары обе партии проиграла, также равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ и, следовательно, количество нециклических троек девушек также равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ .

Задача 023

01.01.2025 от

В однокруговом чемпионате по матбоям участвовали 16 команд из 16 разных школ. Каждый бой проходил в одной из школ-участниц. Могло ли по окончании чемпионата случиться, что каждая команда сыграла во всех школах, кроме своей?

Подсказка

Сколько боёв было сыграно в любой из школ?

Решение

Каждая команда сыграла в чемпионате 15 боев. Чтобы поиграть во всех школах, кроме своей, она должна была сыграть в каждой из них по одному разу. Но это значит, что в любой данной школе за время чемпионата должны были сыграть по одному разу 15 команд (все, кроме своей). Но в каждом бое участвуют две команды, поэтому общее число команд, игравших в данной школе, должно быть чётным. Полученное противоречие показывает, что так, как сказано в условии задачи, случиться не могло.

Задача 031

01.01.2025 от

В чемпионате по волейболу участвовало $n>2$ команд, каждые две из которых сыграли друг с другом ровно один раз. Оказалось, что для каждых двух команд есть ровно $t$ команд, у которых они обе выиграли. Докажите, что $n=4 t+3$ .

Подсказка

Решение

Возьмем любую команду $A$ . Пусть она выиграла у $k$ команд. Тогда каждая из этих $k$ команд выиграла ровно у $t$ из этих $k$ команд — иначе нарушится условие задачи относительно нее и команды $A$ . Общее число матчей в микротурнире между данными $k$ командами равно $k(k-1) / 2$ с одной стороны и общему числу побед, равному $t k$ — с другой, откуда $k=2 t+1$ . Осталось заметить, что в всем турнире было сыграно $n(n-1) / 2$ матчей и одержано $n(2 t+1)$ побед. Значит, $n(n-1) / 2=n(2 t+1)$ , откуда $n=4 t+3$ .

Задача 035

01.01.2025 от

10 команд играют турнир. В некоторый момент оказалось, что любые две команды сыграли между собой не более, чем по одному разу, только «»Металлург»» и «»Локомотив»» сыграли дважды. При этом каждая команда сыграла хотя бы один матч. Могло ли так случиться, что в этот момент все команды сыграли различное число игр?

Подсказка

Допустим, есть команда, не сыгравшая ни одного матча. Тогда каждая из оставшихся команд сыграла не больше 9 матчей: с каждой из остальных восьми плюс один повторный.

Решение

Ответ: Нет. Решение. Допустим, есть команда, не сыгравшая ни одного матча. Тогда каждая из оставшихся команд сыграла не больше 9 матчей: с каждой из остальных восьми плюс один повторный. Получается 9 возможностей $(1,2, \ldots, 9$ матчей) на 19 команд. Но тогда эти команды вместе сыграли $(1+2+\ldots+9) / 2=22,5$ матчей, что невозможно.

Теперь допустим, что каждая команда сыграла хотя бы один матч. Тогда для числа сыгранных матчей получается 10 возможностей $(1,2, \ldots, 10$ матчей) на 10 команд. Но тогда эти команды вместе сыграли $(1+2+\ldots+10) / 2=27,5$ матчей, что также невозможно.

Задача 063

01.01.2025 от

В турнире по бадминтону участвовало 16 спортсменов. Каждые двое сыграли не более одной игры, при этом ничьих не было. После окончания турнира оказалось, что все игроки одержали различное количество побед. Докажите, что все участники потерпели различное количество поражений.

Подсказка

На турнире можно одержать от 0 до 15 побед. Так как это ровно 16 вариантов, то каждый из этих вариантов встретился у одного из спортсменов.

Решение

На турнире можно одержать от 0 до 15 побед. Так как это ровно 16 вариантов, то каждый из этих вариантов встретился у одного из спортсменов. Следовательно, было сыграно $0+1+2+\ldots+15=15 \cdot 14 / 2$ игр, а это все возможные игры, которые могли быть сыграны. Таким образом, каждый участник сыграл 15 игр, у всех участников разное число побед, поэтому и разное число поражений.

Задача 066

01.01.2025 от

В турнире принимает участие 250 команд, каждая играет с каждой один раз дома и один раз на выезде. Можно ли к каждому матчу приставить одного из 10 судей так, чтобы для каждой команды множества судей, которые будут судить у неё дома, и судей, которые будут судить у неё на выезде, не пересекались?

Подсказка

Сопоставим каждой команде свою пятерку судей.

Решение

Ответ. Можно.

Решение. Сопоставим каждой команде свою пятерку судей. Так как $C_{10}^{5}=252>250$ , такое сопоставление возможно. В качестве судьи матча между командами $A$ и $B$ , где для $A$ матч домашний, выберем любого судью, сопоставленного команде $A$ , но не сопоставленного команде $B$ . Тогда у каждой команды домашние матчи судят только пять судей, которые ей сопоставлены, а выездные матчи — только пять судей, которые ей не сопоставлены.

Задача 082

01.01.2025 от

На площадке можно сыграть или в волейбол, или в футбол, или в баскетбол. На площадку пришли 7 команд, и каждая команда сыграла с каждой ровно один матч. Известно, что нет трёх команд, которые друг с другом играли в один и тот же вид спорта. Тройку команд, которые между собой сыграли во все три вида спорта, назовём разносторонней. Какое наибольшее количество разносторонних троек команд могло быть?

Подсказка

Всего троек команд можно составить $7 \cdot 6 \cdot 5 / 2=35$ . Назовем плохой командой не разносторонней тройки ту, которая с двумя другими играла в одну и ту же игру. Так как нет трех команд, которые друг с другом играли в один и тот же вид спорта, в каждой не разносторонней тройке одна плохая команда.

Решение

Ответ. 14.

Решение. Оценка. Всего троек команд можно составить $7 \cdot 6 \cdot 5 / 2=35$ . Назовем плохой командой не разносторонней тройки ту, которая с двумя другими играла в одну и ту же игру. Так как нет трех команд, которые друг с другом играли в один и тот же вид спорта, в каждой не разносторонней тройке одна плохая команда. С другой стороны, каждая команда является плохой самое меньшее в трех тройках. В самом деле, если она играла в один и тот же вид спорта хотя бы с тремя командами, то она образует не разносторонние тройки с каждыми двумя из них. Иначе она играла в каждый вид спорта с двумя командами, и три не разносторонние тройки тоже налицо. Таким образом, не разносторонних троек хотя бы $3 \cdot 7=21$ , а разносторонних — не более $35-21=14$ . Пример. Расставим команды по кругу, и пусть в футбол, баскетбол и волейбол играют между собой те, между которыми по часовой стрелке нет других команд, одна другая команда и две другие команды соответственно. Нетрудно проверить, что тогда получится ровно 14 разносторонних троек.

Задача 087

01.01.2025 от

В первый день $2^{n}$ школьников играли в пинг-понг «навылет»: сначала сыграли двое, затем победитель сыграл с третьим, победитель этой пары — с четвёртым и т.д., пока не сыграл последний школьник (ничьих в пинг-понге не бывает). Во второй день те же школьники разыграли кубок: сначала произвольно разбились на пары и сыграли в парах, проигравшие выбыли, а победители снова произвольно разбились на пары и сыграли в парах, и т.д. Оказалось, что наборы игравших пар в первый и во второй день были одни и те же (возможно, победители были другие). Найдите наибольшее возможное значение $n$ .

Подсказка

Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия).

Решение

Ответ. 3.

Решение. Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия). Тогда соответствующие рёбра образуют путь, а остальные рёбра одним концом примыкают к этому пути. В частности, если выбросить все висячие вершины, то останется только наш путь без крайних вершин.

Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить висячие вершины, останется граф турнира на $2^{n-1}$ победителях первого этапа. Он, очевидно, является путём лишь при $n \leq 3$ , в противном случае победитель турнира будет иметь степень не меньше 3 . Значит, $n \leq 3$ .

Осталось привести пример при $n=3$ . Пусть участники пронумерованы от 1 до 8 и пары в кубке таковы (первым указан проигравший, вторым победитель): $1-2,3-4,5-6,7-8,2-4,6-8$ , $4-8$ тогда при игре навылет пары могли быть такими (победитель снова указан вторым): $1-2$ , $2-4,3-4,4-8,7-8,8-6,6-5$ .

Задача 089

01.01.2025 от

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

Подсказка

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых.

Решение

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых. Если таких пар наберется 25 , среди входящих в них 50 человек не найдется никого, кто был бы знаком с 49 остальными — противоречие. Значит, таких пар не больше 24 , и в них входит не больше 48 человек. Понятно, что среди 52 (или большего числа) остальных людей каждый знает каждого, что и требовалось доказать.