Графы и турниры → .02 Турниры в терминах графов и не только (считаем игры и очки)

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

Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить висячие вершины, останется граф турнира на победителях первого этапа. Он, очевидно, является путём лишь при в противном случае победитель турнира будет иметь степень не меньше Значит,

Осталось привести пример при Пусть участники пронумерованы от до и пары в кубке таковы (первым указан проигравший, вторым победитель): тогда при игре навылет пары могли быть такими (победитель снова указан вторым):

Предположим, что в каком-то туре не было игры между земляками. Тогда участники разбиваются на пары людей из разных городов. Рассмотрим произвольного участника. В каждой паре есть не более одного его земляка, также второй участник из его пары не является его земляком. Но тогда всего земляков у него меньше половины из всех участников. Значит, каждый участник сыграл больше игр с неземляками, чем с земляками, и в сумме игр между земляками было меньше половины. Противоречие.

Из условия видно, что сумма очков, набранных всеми командами, в раза больше числа очков у второй команды. Значит, общая сумма делится на Всего в турнире было игр, а в каждой игре разыгрывалось или очка. Поэтому общая сумма очков не меньше и не больше следовательно, она равна или В первом случае все игр закончились вничью, а во втором ничьих было Но первый случай противоречит тому, что первая команда набрала больше очков, чем вторая.

Всего было фигур, каждая фигура использована раза. Поэтому Н называли только Аня один раз и Глеб три раза. Значит, у Бори и Вовы три раза Б и три раза К.

В сумме набрано баллов. Если бы у Глеба был балл или больше, на месте было бы балла или больше, на втором балла или больше, на первом балла или больше и в сумме было бы баллов или больше. Поэтому у Глеба или баллов. Глеб ни разу не выигрывал и максимум раз сыграл вничью. Аналогично, Аня не могла набрать балла или меньше. Т. е. у Ани или балла. Аня ни разу не проигрывала и максимум раз сыграла вничью.

У Бори и Вовы раза Б и раза К. Значит, вничью с Глебом они сыграть не могли, поэтому оба у него выиграли, поэтому оба показали Глебу К. У одного из них ББК, у другого ККБ.

Теперь рассмотрим случая. Боря и Вова показали друг другу Б. Или Боря и Вова показали друг другу КБ.

Боря и Вова показали друг другу Б. Тогда Ане все три мальчика показали разные фигуры. Если бы Аня хоть один раз сыграла вничью, то другие игры либо тоже вничью, либо одна выигрыш, другая проигрыш. Поэтому Аня вничью с ними играть не могла и должна была все три игры выиграть. Но тогда у Бори и Вовы было бы одинаковое количество баллов балла). Поэтому этот случай невозможен.

Боря и Вова показали друг другу КБ. Тогда Ане оба показали Б. Аня не могла проиграть Глебу, поэтому Глебу она показала не Б. Значит, Б она показала Боре или Вове, сыграв вничью. Поэтому у других двоих она должна была выиграть. Т. е. Глебу показала К, а третьему парню — Н. Аня набрала балла. Если бы в борьбе Бори и Вовы выиграл тот, что сыграл с Аней вничью, у него тоже было бы балла. Поэтому в борьбе Бори и Вовы выиграл тот, который проиграл Ане. И он на месте (2 балла у него). Боря выиграл у Вовы, показав Б. Вова, соответственно, показал Боре К.

Всего команды набрали очков, что кратно команд набрали поровну очков, значит, чемпион тоже набрал число очков, кратное Больше очков в играх он набрать не мог. Но и меньше не мог:  — это среднее число очков, набранных всеми командами, а чемпион набрал больше среднего.

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

Команда, набравшая очков, выиграла хотя бы один матч, иначе набрала бы не больше очков. Из ограничения следует, что она могла выиграть не более двух матчей. Значит, — целое или полуцелое число, в таком случае — делитель числа С другой стороны, поскольку у каждой из первых четырёх команд есть хотя бы одна победа. Следовательно, возможны только два варианта.

Но в этом случае команда, набравшая очков, должна была одержать ровно три победы, т.е. Противоречие.

Что и является ответом.

В каждом матче команды в сумме получают очка, если играют вничью, и если кто-то из них выигрывает. Всего сыграно матчей, следовательно, сумма очков, набранных командами — это число от до причем четное, так как победитель набрал столько же очков, сколько остальные три команды. Предположим, что команды набрали очков, тогда все матчи закончились вничью и условие не выполнено. Приведем пример, когда сумма очков равна (тогда ничьих будет так как любая ничья уменьшает общую сумму очков на

Решение. Заметим, что всего в турнире сыграно боев, а в каждом бое разыгрывается ровно очка. Следовательно, сумма очков всех команд равна Это означает, что единоличный победитель набрал больше, чем очков. Действительно, если он набрал очков или меньше, то и любая другая команда набрала меньше очков, тогда сумма всех набранных очков меньше Приведем пример, когда победитель мог набрать очков.

Так как Буратино отдал сначала золотых, а проиграл то ему вернули золотых, значит, ровно его прогноза были верными. Если верен прогноз (ничья), то автоматически верен и прогноз тогда остальные прогнозы ошибочны, значит, из неверного прогноза следует, что Кроты не пропустили ни одного гола, т.е. матч закончился со счетом Если прогноз — ошибочный, то окажется ошибочным и прогноз т.к. иначе будут верны ещё прогнозы и уже три верных прогноза — противоречие. Значит, ошибочны прогнозы и верны и тогда Кроты выиграли матч, пропустив хотя бы гол, а в сумме с Канарейками забили три, т.е. матч закончился со счётом

Пусть в шахматном кружке групп, а — количество мальчиков в –ой группе, где Тогда в этой группе девочек. Заметим, что игр между мальчиками в этой группе было

А игр между девочками было

Посчитаем разницу между количеством парнтий между мальчиками и девочками во всём турнире:

Итак, мы получили, что число партий между мальчиками больше числа партий между девочками на что кратно 5, а, значит, не может быть равно 23.

Заметим, что борец с номером может проиграть только борцу с номером или , поэтому после каждого тура наименьший номер не может увеличиться больше, чем на номера. На турнире с участниками туров, следовательно, номер победителя турнира не превосходит

Предположим, что борец с номером может победить. Тогда в первом туре должны выбыть борцы с номерами и . Это возможно только если борец с номером проиграл борцу с номером , а борец с номером проиграл борцу с номером . Значит, после первого тура борцы с номерами и останутся.

Аналогично, после второго тура останутся борцы с номерами и , после третьего: и , после седьмого: и Значит, в последнем, финальном, бою встретятся борцы с номерами и . Противоречие с предположением, что борец с номером может победить.

Покажем, что борец с номером 16 может победить. Назовём борцов с номерами большими слабыми. Пусть в туре с номером борец с номером проиграет борцу с номером , борец с номером проиграет борцу с номером , борцы с номерами победят каких-то слабых борцов, оставшиеся слабые борцы как-то сыграют между собой. Тогда после туров останутся борцы с номерами и , и в финальном бое борец с номером победит.

Всего в ходе турнира было сыграно партий, т.е. разыграно столько же очков. По условию, Вася проиграл одну партию, поэтому с участниками он сыграл либо вничью, либо выиграл. Значит, он набрал не менее очков. Тогда каждый из остальных набрал не менее очков, а все шахматисты в сумме набрали не менее очков. Это возможно только в случае, если занявший первое место Петя набрал очков, Вася набрал очков, а остальные участники — по очков.

Рассмотрим некоторую команду Поделим все остальные команды на три группы — те, кого команда выиграла, те, кому проиграла, и те, с кем у ничья(группы могут быть пустыми).

Возьмём две команды и из первой группы, если в этой группе не меньше двух команд. Пусть выиграла Тогда в тройке команд и у 6 очков, у 3 очка, а у — 0, что противоречит условию о том, что для любой тройки команд найдутся две команды из этой тройки, набравшие равное число очков в играх с командами из этой тройки. Аналогично, команда не могла победить то есть между и ничья. А так как и выбраны произвольно, то можно сделать вывод, что между любыми двумя командами из первой группы ничья.

Теперь возьмём две команды и из второй группы. Если выиграла то у 0 очков, у 6 очков, а у — 3, что опять же противоречит условию. Таким образом, между любыми двумя командами из второй группы ничья.

Наконец, возьмём две команды и из третьей группы. Если выиграла то у 2 очка, у 4 очка, а у — 1, что невозможно по условию. Получается, между любыми двумя командами из третьей группы ничья.

Разобьём команды на три подгруппы так, чтобы любые две команды из одной подгруппы сыграли между собой вничью: первая подгруппа это те, кого команда выиграла, вторая — те, кому проиграла, и третья — те, с кем сыграла в ничью и сама команда Первая и вторая подгруппы могут быть пустыми, а значит, всего подгрупп не более трёх, и внутри каждой все команды сыграли вничью.

При победе первой команды ставку возвращают в шестикратном размере, поэтому на неё необходимо поставить более всех денег. Аналогично, на вторую команду необходимо поставить более всех денег, на третью более , на четвертую более . Так как

то существует набор чисел, в сумме дающих единицу, таких, что каждое больше соответствующей дроби. Любой такой набор подходит.

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

Всего в графе есть потенциальных циклических треугольников.

Что может сделать треугольник не циклическим? Либо в нём нет какого-то ребра, либо в нём две стрелки идут в одну вершину. Каждое отсутствующее ребро портит треугольников. Все такие рёбра портят не более треугольников (потому что их ). По условию в каждую вершину входит стрелочки, то есть каждая вершина портит треугольников, а значит, всего таким образом испорчено не более треугольников. К сожалению, Однако по условию из каждой вершины выходит два отсутствующих ребра. То есть если игрок сыграл с и вничью, то рёбра и портят треугольник значит, мы его посчитали дважды.

Таким образом, всего испорчено не более треугольников. Следовательно, хотя бы один будет циклическим.

Оценка. Разрыв меньше двух очков быть не может: при двух командах победитель отличается от проигравшего не менее чем на 2 очка, а при большем числе команд А и Я отличаются как минимум на очко от любой другой команды, причём в разные стороны. 1)Пример. Пусть все встречи, кроме одной, закончились вничью. Тогда победитель этой одной встречи набрал на 2 очка больше проигравшего, а остальные расположились между ними. 2) Пример. Пусть 9 команд (все, кроме А) выиграли друг у друга по кругу (каждая победила и проиграла по разу), А победила Я, а остальные встречи закончились вничью. Тогда у А 11 очков, у Я — 9 очков, а у остальных — по 10.

Каждый, кроме победителя, проиграл один бой. Поэтому, чтобы побед было больше, чем поражений, их должно быть хотя бы две (ясно, что и у победителя не меньше двух побед). Тем самым, 32 боксёра и только они выиграли первые два боя. Но после первых двух боёв остается четверть участников. Следовательно, в турнире участвовало 128 боксеров.

Победитель сыграл 4 матча, в каждом набрал не более трёх очков (причем ровно 3 только в случае победы), значит, всего у него не более 12 очков. Остальные команды в каждом из шести матчей между собой набрали в сумме не менее двух очков (причем 2 только в случае ничьей), поэтому в сумме набрали не менее 12 очков. Указанное в условии равенство достигается только при 12 очках, то есть когда победитель всё выиграл, а все 6 остальных встреч были ничейными.

Пусть в турнире участвовали девочек и мальчиков. Тогда девочки в партиях между собой набрали очков, а мальчики Разница составляет очков. По условию мальчики и девочки в сумме набрали поровну. Значит, девочки набрали больше на очков в партиях между мальчиками и девочками. В этих партиях было всего разыграно очков, поэтому , то есть Но натуральное число, и потому и неравенство обращается в равенство. Значит, в турнире участвовала одна девочка и три мальчика. Девочка набрала не менее очков, следовательно, она выиграла у всех мальчиков и заняла первое место.

Будем называть вершины игроками. Выберем каких-нибудь двух игроков. Один из них выиграл у другого. Выигравшего обозначим A, а проигравшего Б и образуем цепочку из двух игроков, где А стоит перед Б. Пусть В — какой-то третий игрок. Если он выиграл у А, поставим его в начало цепочки. Если он проиграл A, но выиграл у Б, поставим В между A и Б. Если В проиграл обоим, поставим его после Б.

Дальше действуем аналогично: пусть сколько-то игроков уже составляют цепочку с нужным свойством, и пусть игрок И не принадлежит цепочке. Если он выиграл у первого в цепочке, добавим И в начало цепочки. Если нет, найдём последнего игрока в цепочке, который выиграл у И, и поставим И после него. Тогда цепочка по-прежнему будет обладать нужным свойством. Продолжая так, мы включим в цепочку всех игроков.