Тема КОМБИНАТОРИКА

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Графы и турниры

Индукция в графах и теорема Турана

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

Лемма о рукопожатиях

Считаем рёбра

Простой путь, Гамильтонов путь, Гамильтонов цикл

Подвешивание, ранжирование, упорядочивание в графах

Деревья и остовные деревья

Двудольные графы и переформулировки к ним

Связность и связные подграфы (клики)

Паросочетания и лемма Холла

Формула Эйлера для графов и многогранников

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#74912Максимум баллов за задание: 7

Проводится шахматный турнир, в котором участвуют $n$ человек $(n> 2).$ Из-за эпидемической обстановки партии проходят в отдельных помещениях, причем в каждом помещении шахматист может играть только фигурами одного цвета.

Например, если Иван играл черными фигурами в помещении №1, то он уже не сможет сыграть белыми фигурами в этом помещении. Аналогично, если участник играл белыми фигурами в помещении №5, то в этом же помещении он уже не сможет играть черными фигурами. При этом он может снова играть белыми фигурами в помещении №5.

Известно, что каждый участник турнира должен сыграть с любым другим участником ровно одну партию. Организаторы хотят составить такое расписание, чтобы задействовать минимально возможное число помещений. Докажите, что это число равно $⌈log2n⌉.$

Источники: Иннополис-2022 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Давайте попробуем доказать, что нам понадобиться не менее, чем [log_2(n)] (под [x] подразумевается целочисленное x округление вверх) комнат и что именно [log_2(n)] достаточно. Для док-ва первого утверждения давайте для удобства заведём функцию f(n) - искомое кол-во помещений от кол-ва участников. И построим док-во по сильной индукции.

Подсказка 2

Рассмотрите какое-то помещение и разбейте множество игроков на тех, которые играли и не играли белыми фигурами. Что мы можем сказать про кол-во участников в одном из получившихся множеств?

Подсказка 3

В каком-то из множеств не более n/2 элементов, пусть в том, которые играли белыми фигурами, тогда не играли ими не менее n/2 элементов и им хватило на 1 помещение меньше, чем n игрокам, какую оценку мы тогда можем получить на f?

Подсказка 4

f(n) - 1 >= f([n/2]), применяя ПИ индукции получим f(n) - 1 >= [log_2([n/2])] <=> f(n) >= [log_2(n)], теперь осталось придумать пример рассадки.

Подсказка 5

Давайте попробуем переформулировать задачу в терминах ориентированного графа, пусть вершины - шахматисты, ориентируем ребро ij, если i > j (i играет белыми, а j - чёрными). Поставим каждому ребру число k - наибольшее такое число, что в двоичной записи числа i на k-м месте стоит 1, а у j - 0. Осталось только доказать, почему такой пример - верный.

Подсказка 6

Посмотрите, сколько всего может быть цифр в числах i, j и почему рёбрам ij, jl соответствуют разные номера, и задача решена!

Показать доказательство

Пусть $f(n)$ — искомое число помещении в зависимости от количества $n$ участников турнира. Сначала докажем индукцией по $⌈log n⌉ 2$ , что $f(n)≥ ⌈log2n⌉.$ База $($ для $n = 3$ и $n = 4)$ очевидна.

Зафиксируем помещение (например, №1) и обозначим через $U1$ множество шахматистов (вершин графа, каждое ребро которого соответствует определенной партии), которые играли в этом помещении белыми фигурами. Аналогично, обозначим за $U2$ множество шахматистов, которые не играли в этом помещении белыми фигурами. Множества $U1$ и $U2$ не пересекаются — значит, хотя бы одно из них $($ без ограничения общности будем считать, что это $U1)$ содержит не более $n∕2$ элементов, остальные шахматисты (их не менее $n∕2$ ) не играли белыми фигурами в помещении №1 — значит, им для этого хватило $f(n)− 1$ помещений:

f(n)− 1≥ f(⌈n∕2⌉)≥ ⌈log2(⌈n∕2⌉)⌉

f(n)≥⌈log2n⌉

Покажем, как сделать "правильное"(т.е. соответствующее условию задачи) расписание с $f(n)=$ $⌈log n⌉. 2$ Для этого занумеруем вершины графа (т.е. шахматистов) числами от $0$ до $n − 1$ и ориентируем ребра графа (т.е. партии) $ij,$ если $i> j$ (шахматист $i$ играет белыми, а $j$ — черными), а помещения занумеруем числами от $0$ до $⌈log2n⌉.$ Ребру $ij$ поставим в соответствие номер $k,$ который определяется как наибольшее $k,$ такое, что в двоичной записи числа $i$ на $k$ -м месте стоит 1, а у числа $j$ — $0.$ Такое $k$ существует, поскольку $i⁄= j.$ Кроме того, в двоичных разложениях $i,j$ не более $⌈log2n⌉$ цифр, откуда $k ≤⌈log2n⌉.$

Осталось проверить, что ребрам $ij$ и $jl$ соответствуют разные номера. Действительно, если бы им соответствовал общий номер $k,$ то у числа $j$ в $k$ -м разряде двоичной записи стояла бы и цифра $0$ $($ из-за ребра $ij),$ и цифра $1$ $($ из-за ребра $jl),$ что невозможно.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#92037Максимум баллов за задание: 7

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

Показать ответ и решение

Минимальная возможная сумма очков, набранных командами, равна $1 +2+ 3+ 4+ 5= 15.$ За одну игру можно набрать максимум 3 очка (в сумме у двух игравших команд). Значит, игр было не менее 5. Однако если было бы ровно 5 игр, то все игры должны были бы закончиться победой одной из команд, а тогда никакая команда не набрала бы ровно 1 очко. Значит, игр минимум $6.$

Пример результатов турнира, в котором было сыграно ровно 6 игр, зададим таблицей.

$PIC$

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 43#100098Максимум баллов за задание: 7

В школьном спортзале один стол для настольного тенниса. Учитель физкультуры организовал школьный турнир. Он вызывает на игру любых двух участников турнира, еще не встречавшихся друг с другом. Ничьих не бывает. Если участник игры терпит второе поражение, то он выбывает из турнира. После того, как было проведено $29$ игр, из турнира выбыли все участники, кроме двух. Сколько школьников участвовало в турнире?

Источники: Муницип - 2022, Мурманская обл., 7.5 (см.tasks.olimpiada.ru)

Показать ответ и решение

Каждый участник выбывает, потерпев ровно два поражения. В ситуации, когда остались двое “финалистов”, общее количество поражений равно 29. Если из турнира выбыло $n$ человек, то они суммарно потерпели $2n$ поражений, а на счету “финалистов” могло быть $0(0+0),1(0+ 1)$ или $2(1+1)$ поражения. Учитывая, что $2n$ и $2n+ 2$ — чётные числа, приходим к уравнению $2n +1 =29$ , откуда $n =14$ , а общее количество участников равно 16.

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 44#100100Максимум баллов за задание: 7

В $3000$ -м году чемпионат мира по хоккею будет проходить по новым правилам: за победу будут давать $12$ очков, за поражение вычитать $5$ очков, а за ничью команды очков не получат. Если на этом чемпионате сборная Бразилии сыграет $38$ матчей, наберет $60$ очков и хотя бы один раз проиграет, то сколько побед она может одержать? Приведите все возможные варианты. В ответ введите все варианты по возрастанию через пробел.

Источники: Муницип - 2022, Башкортастан, 7.5 (tasks.olimpiada.ru)

Показать ответ и решение

Пусть в $x$ матчах Бразилия победит, а в $y$ матчах проиграет. Составим уравнение $12x− 5y =60$ . Видим, что $12x..12 .$ и $60..12 .$ . НОД $(5,12)= 1$ , т.е. $.. y.12.$

а) $y = 12$ . Тогда получим уравнение $12x− 60 =60$ . Т.е. $x =10$ . Это возможно.

б) $y = 24$ . Получим уравнение: $12x− 120= 60$ . Откуда $x= 15$ . Это невозможно, т.к. количество матчей уже превышает 38.

в) $y = 36$ . Получим $12x− 180= 60$ . Откуда $x =20$ , что также невозможно. Большие значения х не подходят, т.к. уже будет превышено число сыгранных матчей.

Ответ: 10

Ошибка.
Попробуйте повторить позже

Задача 45#72179Максимум баллов за задание: 7

Шахматный турнир прошёл по круговой системе, где каждый участник сыграл с каждым один раз. Назовём партию неправильной, если выигравший её шахматист в итоге набрал очков меньше, чем проигравший. (Победа даёт $1$ очко, ничья — $1∕2,$ поражение — $0$ ). Могут ли неправильные партии составлять более $75%$ от общего количества партий в турнире?

Источники: Муницип - 2021, Бурятия, 11.5

Подсказки к задаче

Подсказка 1

Введём для начала обозначения. Пусть всего игроков было N. И давайте выделим половину участников турнира, пусть M= [N/2]. Тогда первые M людей будут сильными, а остальные слабыми. Как теперь можно задачу в таком виде удобно для нас переформулировать?

Подсказка 2

Верно, давайте проверим, могли ли "правильные" партии составлять меньше 25% от общего числа. Поняв это, мы поймём и ответ на нашу задачу. Получается правильные партии это те, в которых сильные выигрывали слабых. Пусть их количество X. Тогда подумайте, что нам нужно глобально посчитать и сравнить в задаче?

Подсказка 3

Ага, давайте посчитаем такие величины, как среднее количество очков сильных и слабых. Тогда если есть неправильные партии, то не все игроки набрали поровну, и средний результат сильного больше, чем слабого. Попробуйте сравнить две этих величины. Помните, что в итоге вам важен X. Что тогда получается?

Подсказка 4

Верно, выразив в неравенстве X, получим оценку на него. Но мы выражали M через N. То есть можно ещё примерно оценить X через N. В итоге, получается какое-то неравенство с этими переменными. Но почему же это почти решило нашу задачу? Потому что нам известно общее число партий! Посчитайте их и увидите, что правильных партий больше 25%. Победа!

Показать ответ и решение

Пусть $N$ — число игроков, $M = [N∕2].$

Игроков, занявших первые $M$ мест, назовём сильными, а остальных – слабыми (между участниками с одинаковой суммой очков места распределяются произвольно). Пусть $X$ — число правильных партий между сильными и слабыми.

Сумма очков, набранных сильными во встречах между собой, равна $M(M−1) 2 ,$ а во встречах со слабыми — не больше $X.$

Поэтому средний результат сильного не больше $M−-1 X- 2 + M.$ Аналогично, средний результат слабого не меньше $N−M-−1 M(N−M-)−X- 2 + N −M .$

Если есть неправильные партии, то не все игроки набрали поровну, и средний результат сильного больше, чем слабого. Отсюда

M (N − M ) N (N − 1) X >----2----≥ ---8---

Так как общее число партий равно $N(N2−1),$ доля правильных партий больше $1∕4,$ то есть более $25$ процентов.

Варианты правильных ответов:

нет
Нет
нельзя
Нельзя

Ошибка.
Попробуйте повторить позже

Задача 46#110673Максимум баллов за задание: 7

Несколько команд сыграли турнир в один круг, причём ничьих не было. Оказалось, что среди любых $100$ команд есть команда, выигравшая у всех остальных $99$ команд, но нет команды, проигравшей всем остальным $99$ командам. Какое наибольшее число команд могло участвовать в турнире?

Подсказки к задаче

Подсказка 1

Пусть домен команды — множество команд, проигравших данной команде. Если мощность домена команды не меньше 99, то команду будем называть доминатором! Легко видеть, что доминаторов не менее n-99, где n — число команд. Посмотрим на доминатора с наименьшим по мощности доменом. Что можно сказать об этом домене?

Подсказка 2

Верно! У всех команд этого домена выиграли все доминаторы. Тогда в этом домене нет доминаторов. Помимо этого, в рассматриваемом домене есть команда, которая проиграла хотя бы 49 командам в этом домене. А какое тогда наибольшее число доминаторов может быть в игре?

Подсказка 3

Верно! В игре не более 49 доминаторов. Тогда n - 99 ≤ 49, и мы получили оценку! Ясно, что пример нужно строить так, чтобы в нем было 49 доминаторов, которые выиграли остальные 99 команд. А как можно распределить результаты боев между доминаторами?

Показать ответ и решение

Оценка. Назовём доменом команды совокупность всех команд, у которых она выиграла. Команду, в домене которой не менее $99$ команд, назовём доминатором.

Пусть в турнире участвовали $n$ команд. Возьмём любые $100$ из них. По условию среди них есть доминатор. Заменим его одной из оставшихся команд. В получившейся сотне снова есть доминатор. Повторяя описанную процедуру, пока не побывавшие в сотне команды не закончатся, убеждаемся, что доминаторов у нас по крайней мере $n− 99.$

Пусть доминатор $A$ имеет домен $P$ с наименьшим числом команд. Покажем, что тогда у команд из $P$ выиграли все доминаторы. В самом деле, пусть есть доминатор $B$ с доменом $Q,$ куда не входит какая-то команда $K$ из $P.$ Тогда в силу минимальности домена $P$ в домене $Q$ есть команда $M,$ не входящая в $P.$ Если $B ⁄= K$ и $A⁄= M,$ то в сотне $S$ команд, составленной из $A,B,K,M$ и любых $96$ команд из домена $P,$ нет команды, победившей все остальные: такой командой может быть только $A$ или $B,$ но $B$ проиграла $K,$ а $A$ проиграла $M.$ Если $B = K,$ дополним $S$ до сотни ещё одной командой из $P.$ Тогда $A$ проиграла $M,$ а $B$ проиграла $A.$ Случай, когда $A = M,$ аналогичен, а случай, когда одновременно $B = K$ и $A= M,$ невозможен.

Так как в домене $P$ не меньше $99$ команд, там есть команда $L,$ проигравшая хотя бы $49$ командам из этого домена — иначе суммарное число поражений в матчах команд из $P$ между собой будет меньше суммарного числа побед. Тогда доминаторов не больше $49$ — иначе, взяв $50$ доминаторов, команду $L$ и $49$ победивших её команд из домена $P,$ мы получили бы сотню (так как в домене $P$ в силу доказанного выше нет доминаторов), в которой команда $L$ проиграла всем остальным. Отсюда $n − 99≤ 49,$ то есть $n ≤148.$

Пример. Разделим $148$ команд на $49$ доминаторов и $99$ доминируемых, проигравших всем доминаторам. Доминируемые команды расположим по кругу, и пусть каждая из них выиграет у $49$ следующих за ней по часовой стрелке и проиграет остальным. Доминаторов занумеруем от $1$ до $49,$ и пусть в каждом матче между ними побеждает команда с большим номером. Тогда в любой сотне команд будет хотя бы один доминатор, и доминатор с наибольшим номером победит все остальные команды. С другой стороны, в этой сотне будет хотя бы $51$ доминируемая команда, и потому каждая из них победит по крайней мере одну из оставшихся, а каждый доминатор победит их все. Таким образом, команды, проигравшей всем остальным, в сотне не будет.

Ответ:

$148$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 47#41594Максимум баллов за задание: 7

В турнире по шахматам каждый из 10 игроков сыграл с каждым по одной партии, и Петя занял последнее место (набрал меньше очков, чем любой другой участник). Потом двоих игроков дисквалифицировали, и все очки, набранные во встречах с ними, аннулировали, и этих двух игроков исключили из таблицы. Оказалось, что в результате Петя стал победителем турнира (набрал больше очков, чем любой другой участник). Сколько очков в итоге (после дисквалификации игроков) мог набрать Петя? За победу дается 1 очко, за ничью — $0,5$ очка, за поражение — $0$ очков.

Источники: Муницип - 2020, Московская область, 8.4

Подсказки к задаче

Подсказка 1

В турнире с 10 игроками, проходящем в 1 круг, разыгрывается 10⋅9/2= 45 очков. Какое наибольшее количество очков мог набрать участник, занявший абсолютное последнее место?

Подсказка 2

Верно, 4! Ведь иначе он набрал хотя бы 4,5, а это значит, что остальные набрали хотя бы 5, т.е. всего хотя бы 49,5 очков. А какое наименьшее количество очков мог набрать победитель турнира, в котором было 8 участников?

Подсказка 3

Верно, тоже 4! Ведь иначе он набрал не более 3,5, а это значит, что остальные набрали не более 3, т.е. всего не более 24,5 очков, а всего их 7⋅8/2=28. Сколько тогда очков мог набрать Петя?

Подсказка 4

И снова верно, 4! Ведь он стал победителем турнира среди восьми человек и абсолютным проигравшим в турнире среди 10 человек, а это значит, что количество его очков не меньше 4 и не больше 4, т.е. 4.

Показать ответ и решение

В турнире с 10 игроками, проходящем в 1 круг, разыгрывается $10⋅9= 45 2$ очков. Поэтому найдется игрок, набравший не более $45:10= 4,5$ очков. Значит, игрок, занявший абсолютное последнее место, набрал не более 4 очков. Аналогично, в турнире с $10− 2= 8$ игроками, проходящем в 1 круг, разыгрывается $8⋅7 2 = 28$ очков. В таком турнире найдется игрок, набравший не менее $28:8= 3,5$ очков. Значит, игрок, занявший абсолютное первое место (после примененной дисквалификации), набрал не менее 4 очков. Таким образом, Петя мог набрать только 4 очка.

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 48#101072Максимум баллов за задание: 7

В турнире по шахматам каждый из $10$ игроков сыграл с каждым по одной партии, и Петя занял последнее место (набрал меньше очков, чем любой другой участник). Потом одного игрока дисквалифицировали, и все очки, набранные во встречах с ним, аннулировали, и этого игрока исключили из таблицы. Мог ли в результате Петя стать победителем турнира (набрать больше очков, чем любой другой участник)?

Источники: Муницип - 2020, 10 класс

Подсказки к задаче

Подсказка 1

Мы знаем количество игр, поэтому можем посчитать количество очков! Оно равно 10*9/2 = 45. Как оценить количество очков, которое набрал абсолютный победитель (до того, как одного участника исключили) и сколько в таком случае максимально мог набрать Петя?

Подсказка 2

45/10 = 4.5 — минимальное количество очков, которое набрал победитель. А значит, Петя мог набрать не более 4 очков. Что получится, если мы сделаем такое же действие, но для турнира на 9 человек? (то есть после того, как одного удалили)

Подсказка 3

В турнире на 9 человек, количество очков — 9*8/2 = 36. Значит победитель набрал не менее 4 очков!

Показать ответ и решение

В турнире с 10 игроками, проходящем в 1 круг, разыгрывается $10⋅9= 45 2$ очков. Поэтому найдется игрок, набравший не более $45:10= 4,5$ очков. Значит, Петя, занявший абсолютное последнее место, набрал не более 4 очков. Аналогично, в турнире с $10− 1 =9$ игроками, проходящем в 1 круг, разыгрывается $9⋅8 2 = 36$ очков. Остальные 8 игроков набрали не менее 32 очков. Значит, найдется игрок (отличный от Пети), набравший (после пересчета) не менее $32:8= 4$ очков. Поэтому Петя не мог стать абсолютным победителем турнира.

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 49#101078Максимум баллов за задание: 7

Четырнадцать теннисистов сыграли в однокруговом турнире (каждый игрок сыграл с каждым одну партию). Докажите, что найдутся такие три игрока, что каждый из остальных $11$ игроков проиграл хотя бы одному из этой тройки. (Ничьих в теннисе не бывает).

Источники: БИБН-2020, 11.3 (см. www.unn.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Из четырнадцати игроков гарантированно будет один, одержавший семь побед. Этот точно в нашей тройке. Подумайте, как повторить такой же принцип ещё два раза.

Подсказка 3

Давайте рассмотрим всех теннисистов, кроме того, кто одержал 7 побед и тех, кого он победил. Теперь среди оставшихся шести теннисистов выберем «самого сильного». Сколько побед он гарантировано одержал?

Показать доказательство

Сначала покажем, что найдется игрок, одержавший не менее семи побед. Действительно, в противном случае общее число побед всех игроков было бы не более $14⋅6= 84$ . Но общее число побед равно числу всех сыгранных партий, то есть равно $(14⋅13) 2 = 91$ — противоречие.

Выберем теннисиста, скажем, $A$ , одержавшего не менее 7 побед. Удалим (временно из рассмотрения) $A$ и семерых, проигравших ему. Останется группа из 6 теннисистов. Рассуждая аналогично, в этой группе найдем игрока $B$ , который выиграл не менее трёх партий у игроков из этой группы. Если убрать из рассмотрения $B$ и троих, проигравших ему, останутся два теннисиста. Из этих двоих выберем того, скажем, $C$ , кто победил другого. Тогда тройка игроков $A,B,C$ будет искомой по построению (первые семеро, удаленные из рассмотрения, проиграли $A$ , удаленная группа из троих проиграла $B$ , и последний проиграл $C$ ).

Ошибка.
Попробуйте повторить позже

Задача 50#38860Максимум баллов за задание: 7

В футбольном турнире играли восемь команд: каждая команда по одному разу сыграла с каждой. В следующий круг отбираются команды, набравшие пятнадцать и более очков. За победу даётся $3$ очка, за ничью — $1$ очко, за поражение — $0$ очков. Какое наибольшее количество команд может выйти в следующий круг?

Источники: ОММО-2019, номер 2, (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1!

Так, посмотрим, мы хотим посчитать количество команд, получивших хотя бы 15 очков. Но ведь количество очков, разыгрваемое в турнире, ограничено! Сколько баллов у нас за игру получают в сумме обе команды?

Подсказка 2!

Ага, таким образом за каждую игру в сумме разыграли не более 3 баллов. То есть мы можем посчитать, сколько всего очков максимально было разыграно за турнир! И посмотрим, сколько команд "пятнидцатибальников" максимально вместится в наше соревнование...

Подсказка 3!

Не забудем доказать, что столько найдется! Осталось аккуратно построить пример :)

Показать ответ и решение

Всего игр было $8⋅7 = 28 2$ , так что разыграно не более $28⋅3= 84$ очков. Отсюда команд, которые набрали хотя бы $15$ баллов, не больше пяти.

Покажем, что такие пять команд найдутся. Пусть каждая из них выиграла у оставшихся трёх, то есть каждой остаётся набрать $6$ очков до $15$ или выиграть ещё два раза. Расположим эти $5$ команд по кругу. Пусть каждая выиграет у следующей по кругу и идущей через одну, то есть, например, $1$ у $2$ и $3$ или $5$ у $1$ и $2$ . Это эквивалентно построению всех рёбер полученного пятиугольника, а также всех диагоналей, поскольку $2 C5 = 10$ , то их как раз $10$ и каждую мы построим по одному разу.

Ответ:

$5$

Ошибка.
Попробуйте повторить позже

Задача 51#42193Максимум баллов за задание: 7

В однокруговом шахматном турнире (каждый шахматист играет с каждым одну партию) участвовало 20 шахматистов, причём 6 из них – из России. Известно, что набрав очков больше, чем кто-либо, первое место занял россиянин Владимир. Второе место занял Левон из Армении, также опередив по очкам каждого из остальных 18 шахматистов. Какое наибольшее суммарное количество очков могли набрать российские шахматисты? (В шахматах за победу в партии даётся одно очко, за ничью – пол-очка, за поражение очков не дают.)

Источники: Муницип - 2019, Свердловская область, 11.6

Подсказки к задаче

Подсказка 1

Заметим для начала, что в каждой игре разыгрывается одинаковое кол-во очков (1+0 = 0+1 = 0.5+0.5). В этой задачке спрашивается про суммарное кол-во очков какой-то команды, а в силу того, что за каждую игру разыгрывается одинаковое кол-во очков, то при любых исходах между участниками команды, вся команда получает фиксированное кол-во очков. Это очень популярный сюжет в таких играх, где мы получаем "бесплатно" минимальное кол-во очков, которое заработала команда за турнир.

Подсказка 2

Давайте попробуем построить пример и доказать, что он подходит. Мы уже поняли, что между россиянами партии приносят один и тот же результат, тогда хотелось бы, чтобы они выиграли у каждого иностранца, кроме Владимира и Левона, потому что им нужно много очков, чтобы быть на 1-ом и 2-ом местах соответственно. Можно попробовать примерно оценить, сколько получит россиянин очков, посчитав кол-во игр между россиянами и россиянами с иностранцами. Попробуйте построить пример, где суммарное кол-во очков у россиян равно 96.

Подсказка 3

Перейдём к оценке, покажем, что 96,5 и более не могло получиться. Попробуйте посчитать кол-во очков, которые разыгрывались между россиянами и иностранцами, а затем понять, сколько максимум очков мог получить иностранец.

Подсказка 4

Верно, каждый иностранец не мог получить больше 2,5 очков, тогда даже, если он победит всех оставшихся иностранцев, то получит не более 15,5 очков. Что мы тогда можем сказать про максимальное кол-во очков, которые мог набрать россиянин при условии, что его должен обогнать иностранец - Левон? А сколько тогда должен набрать Владимир при условии, что россияне набрали не менее 96,5 баллов?

Показать доказательство

Приведем пример, показывающий, что суммарно российские шахматисты могли набрать 96 очков. Пусть Владимир выиграл все свои партии, кроме партии с Левоном, которая завершилась вничью. Пусть, кроме того, Левон сыграл вничью и со всеми остальными россиянами, а у не россиян неизменно выигрывал. Наконец, пусть все остальные партии между россиянами завершились вничью, а иностранцев, кроме Левона, все россияне победили. Тогда Владимир набрал $18⋅1+1 ⋅0,5= 18,5$ очков, Левон набрал $13⋅1+ 6⋅0,5 =16$ очков, каждый из остальных россиян набрал $13 ⋅1 +5⋅0,5= 15,5$ очков, а каждый из остальных тринадцати игроков - не более, чем 12 очков. Условие задачи в этом случае выполнено, а количество очков набранных всеми россиянами равно $18,5+5 ⋅15,5= 96$

Покажем, методом от противного, что больше очков россияне набрать не могут. Пусть они в сумме набрали 96,5 очков или больше. В 15-и партиях между собой они взяли в сумме 15 очков, а остальные (не менее 81,5 $)$ взяты в партиях с представителями других стран. Таких партий россиянин - не россиянин было $6⋅14= 84$ , и в них разыгрывалось всего 84 очка. Тогда все иностранцы в партиях с россиянами набрали не более 2,5 очков, и никто из них, в том числе Левон, не мог набрать в сумме более, чем $13+ 2,5 =15,5$ очков. Пятеро россиян, которых он опередил, набрали при этом не более 15 очков каждый, а тогда Владимир должен набрать не менее $96,5− 15⋅5= 21,5$ очка. Но он сыграл всего 19 партий, и потому набрать более 19 очков не мог. Противоречие.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 52#80506Максимум баллов за задание: 7

В однокруговом турнире по настольному теннису приняло участие 35 человек. По итогам турнира оказалось, что нет такой четверки игроков $A,B,C,D$ , что $A$ выиграл у $B,B$ — у $C,C$ — у $D$ , а $D$ — у $A.$ Каково наибольшее количество троек участников, одержавших во всех трех встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.

Подсказки к задаче

Подсказка 1

Как из двух троек можно получить четвёрку?

Подсказка 2

У них должны быть 2 общих участника. Что тогда можно сказать о полученной четвёрке?

Подсказка 3

Докажите, что тройки не пересекаются, и получите оценку на их количество.

Показать ответ и решение

Пусть есть $2$ тройки, которые пересекаются по ребру. Назовем их $A,B,C$ и $A,B,D.$ Тогда не умаляя общности $A$ выиграл у $B$ и $C$ выиграл у $D,$ $B$ выиграл у $C$ и $D,$ а $A$ проиграл $C$ и $D$ . Тогда $A$ выиграл у $B,$ $B$ выиграл у $C,$ $C$ выиграл у $D,$ а $D$ выиграл у $A$ ?!

Пусть есть 2 тройки, которые пересекаются по вершине. Назовем их $A,B,C$ и $C,D,E$ . Тогда без ограничения общности $C$ выиграл у $A$ и $D$ и $D$ выиграл у $A,$ $A$ выиграл у $B,$ $B$ выиграл у $C$ , $D$ выиграл у $E$ и $E$ выиграл у $C.$ Тогда $A$ выиграл у $B,$ $B$ выиграл у $C,$ $C$ выиграл у $D,$ а $D$ выиграл у $A$ ?!

Значит, тройки не пересекаются и их не более 11. Осталось показать, что 11 троек может быть. Давайте выделим 11 непересекающихся троек и еще двойку и пронумеруем их от 1 до 14. В каждой тройке у нас будет цикл, в двойке победа будет у любого, а между группами $i$ и $j$ (где $i⁄= j)$ победа будет у группы с большим номером. Тогда если появится запретная четверка, то заметим, что если обходить ее по кругу от проигравшего к победителю, то номер группы может только расти или не изменяться. Раз мы вернемся в конце в начальную вершину, то номер группы должен все время не изменяться, и значит, все 4 вершины лежат в одной группе?! Значит, запретных четверок в таком турнире не будет.

Ответ: 11

Ошибка.
Попробуйте повторить позже

Задача 53#98108Максимум баллов за задание: 7

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

Показать ответ и решение

Пусть в турнире участвовало $n$ команд, причём команда-победитель выиграла $k$ матчей. Тогда каждая из оставшихся $n− 1$ команд выиграла по $k− 2$ матча. Всего между командами состояпось $n(n−-1) 2$ матчей, в которых суммарно было $n(n−1) 2$ победителей. С другой стороны, суммарное число побед всех команд равно $k+(n− 1)(k− 2)$ . Значит,

n(n− 1) k+ (n − 1)(k − 2)=--2---

kn= 2(n − 1)+ n(n−2-1)-= (n-+4)2(n-− 1)

k = (n+-4)(n-− 1)k 2n

является целым числом, следовательно,

2k = (n-+4)(n-− 1)= n− 3− 4 n n

целое число, а значит $-4 n$ — целое, что возможно лишь при $n= 1,n =2,n= 4$ .

При $n =1$ матчей не было.

При $n =2$ число $k = 32$ , что не является целым.

При $n =4$ число $k = 3$ .

Пример: занумеруем команды числами $1,2,3,4$ . Команда 1 вынграла у всех, команда 2 выиграла у команды 3, команда 3 выиграла у команды 4, команда 4 выиграла у команды 2.

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 54#34057Максимум баллов за задание: 7

$20$ команд сыграли однокруговой турнир матбоев. За победу дается $2$ балла, за ничью — $1$ балл, за поражение — $0$ баллов. После того, как жюри упорядочило команды по убыванию набранных баллов, оказалось, что разница между набранными баллами любых двух соседних команд одна и та же. Сколько баллов могли набрать победители турнира?

Источники: Лига открытий - 2018

Показать ответ и решение

Заметим, что разница между баллами соседних команд не больше $2,$ ведь при разнице $3$ или больше победитель набирает не меньше $19⋅3= 57$ очков, что невозможно, ведь максимальное число баллов, которое можно набрать, равно $38.$ Если разница равна $2,$ то победитель набирает не больше $38$ только в случае, если у последней команды $0$ баллов, а у первой — в точности $38$ баллов, и пример на это количество легко строится, когда каждая команда обыграла всех ниже нее в списке. Тут же отметим, что также возможна разница $0 :$ тогда все команды набирают по $19$ баллов, например, играя вничью.

Пусть разница может быть равна $1.$ Сумма всех набранных баллов равна $(20⋅19 :2)⋅2= 380.$ Разобьем все команды на пары: первая-последняя, вторая-предпоследняя, и т. д., десятая-одиннадцатая. В каждой паре команды набрали одинаковое число баллов, а именно $380:10= 38.$ Но баллы десятой и одиннадцатой команд разной четности, поэтому такое невозможно.

Ответ:

$38$ или $19$

Ошибка.
Попробуйте повторить позже

Задача 55#41750Максимум баллов за задание: 7

Андрей, Борис, Василий, Геннадий и Дмитрий играли в настольный теннис парами так, что каждые двое сыграли с каждой другой парой ровно один раз. Ничьих в теннисе не бывает. Известно, что Андрей проиграл ровно 12 раз, а Борис ровно 6 раз. Сколько раз выиграл Геннадий?

Источники: Муницип - 2018, Саратовская область, 8.2

Подсказки к задаче

Подсказка 1

Для начала, давайте вообще посчитаем кол-во игр. Их 15. А теперь посмотрите на Андрея: он проиграл очень много игр...В скольких играх он в принципе участвовал?

Подсказка 2

Он участвовал в 12 играх, как раз столько, сколько он проиграл) Значит, все кто играл с ним в команде - проиграли эту игру. Попробуйте дальше посчитать кто сколько проиграл и сколько выиграл, считая еще при этом кто с кем играл)

Показать ответ и решение

Первую пару можно составить $5× 4:2= 10$ способами, вторую пару можно составить $3×2 :2 =3$ способами. Всего игр получаем $10× 3:2= 15.$ Андрей всего играл в 4 парах, а они играли с 3 парами. Значит, всего Андрей играл 4×3=12 раз. По условию, он проиграл 12 раз, следовательно, он проиграл все свои игры. Вместе с ним в паре 3 раза проиграл Борис. Поскольку Борис выиграл у Андрея 6 раз, когда играл в паре с Василием (2 раза), с Геннадием, с Дмитрием, то остальные он партии проиграл, то есть 3 с Андреем и по одной с Василием (против Геннадия и Дмитрия), с Геннадием и с Дмитрием. Значит, Геннадий проиграл с Андреем 3 раза и с Борисом 1 раз, всего 4 раза. Поэтому выиграл он 8 раз.

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 56#74606Максимум баллов за задание: 7

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

Источники: Миссия выполнима 2018

Подсказки к задаче

Подсказка 1

Давайте скорее перейдём от этих длинных условий к красивому математическому уравнению. Нам понадобятся всего 3 переменные: n - кол-во игроков, k - кол-во игроков в первой группе, m - партии между разными группами. Если внутри группы были сыграны все игры, то у нас получился полный граф на k вершинах. А сколько рёбер в полном графе на k вершинах?

Подсказка 2

Верно k*(k-1)/2. Теперь у нас есть все знания, чтобы составить уравнение на кол-во партий.

Подсказка 3

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

Подсказка 4

Да, лучше решать относительно k, ведь тогда в дискриминанте будет участвовать n, а это хорошо, потому что, с одной стороны, у нас получится неравенство, и мы сможем оценить n сверху, а с другой - в нашем неравенстве не будет k, которое противно связано с нашим n тем, что k < n.

Подсказка 5

Ура, мы получили понятные выражения на n и можем воспользоваться тем, что 0 < m <= 4, к сожалению, нам теперь остаётся только оценить большее из них и пытаться найти пример или доказывать, что такого не бывает.

Подсказка 6

Из наших выражений следует, что n <= 20, не бойтесь перебирать каждое из них с конца и подставлять в исходное квадратное уравнение. Так же помните, что k - целое, да ещё и в силу того, что в другой команде n-k игроков, то не имеет особого смысла рассматривать k < n/2, это такой же случай, просто мы поменяли местами номера команд.

Показать ответ и решение

Пусть число участников турника равно $n,$ а число попавших в $1$ -ю группу равно $k$ . Тогда число сыгранных партий равно:

k(k− 1) (n − k)((n− k)− 1) ---2-- + ------2-------+ m = 99,

где $0 <m ≤ 4$

k2− k+ (n − k)2− (n − k)+ m − 198= 0

k2 − k+ k2− 2kn +n2− n+ k+ 2m− 198= 0

2 2 2k − 2kn+ (n − n +2m − 198)= 0;

D-=n2 − 2(n2− n +2m − 198)≥ 0 4

(n− 1)2− (397− 4m)≤ 0

откуда $√------- nmax =1+ 397− 4m≤ 20.$

Если $n= 20,$ то:

2k2− 40k+(400− 20+ 2m − 198)= 0⇔

⇔ k2− 20k +91+ m = 0,

тогда $k= 10,n− k = 10,m =9$ - противоречие;
$k =11,n− k= 9,m = 8$ - противоречие;
$k =12,n− k= 8,m = 5$ - противоречие;
$k =13,n− k= 7,m = 0$ - противоречие;
при $k > 13$ и $m < 0.$

Если $n= 19,$ то:

2k2− 38k+(361− 19+ 2m − 198)= 0⇔

⇔ k2− 19k +72+ m = 0,

тогда $k= 10,n− k = 9,m = 18$ - противоречие;
$k =11,n− k= 8,m = 16$ - противоречие;
$k =12,n− k= 7,m = 12$ - противоречие;
$k =13,n− k= 6,m = 6$ - противоречие;
при $k > 13$ и $m < 0.$

Если $n= 18,$ то:

2k2− 36+ (324− 18+ 2m − 198)= 0⇔

⇔ k2− 18+ 54+ m= 0,

тогда $k= 9,n− k= 9,m = 27$ - противоречие;
$k =10,n− k= 8,m = 26$ - противоречие;
$k =11,n− k= 7,m = 23$ - противоречие;
$k =12,n− k= 6,m = 18$ - противоречие;
$k =13,n− k= 5,m = 11$ - противоречие;
$k =14,n− k= 4,m = 2$ - решение.
при $k > 13$ и $m < 0.$

Итак, наибольшее возможное число участников равно $18$ , группы участников насчитывают $4$ и $14$ человек, количество «межгрупповых» партий равно $2$ .

Ответ: 18

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 57#91400Максимум баллов за задание: 7

В футбольном чемпионате Анчурии принимают участие 18 команд. Каждое воскресенье проходит очередной тур: все команды разбиваются на пары и в каждой паре проходит футбольный матч. Уже прошло 8 туров, при этом никакие две команды не играли между собой более одного раза. Верно ли, что тогда обязательно можно найти три команды, среди которых никакие две между собой не играли?

Источники: Муницип - 2018, Ярославская область, 11.5

Показать ответ и решение

Рассмотрим одну из команд, обозначив ее через $A.$ Так как за 8 туров она сыграла с восемью командами, то с девятью она не сыграла. Если среди этих девяти есть две команды $B$ и $C$ , не сыгравшие между собой, то $A,B$ и $C$ образуют искомую тройку команд.

В противном случае эти 9 команд сыграли между собой полный круговой турнир. Для этого потребовалось $9⋅8 2 = 36$ матчей. Однако, в каждом туре они могли играть между собой не более четырех матчей, поэтому за 8 туров таких матчей могло быть сыграно не более $32.$ Полученное противоречие показывает, что искомая тройка команд обязательно найдется.

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 58#96451Максимум баллов за задание: 7

Шесть теннисистов провели круговой турнир, сыграв по разу каждый с каждым. В итоге оказалось, что теннисисты, разделившие первое-второе места, набрали поровну очков, теннисисты, разделившие два последних места, также набрали поровну очков, а теннисисты, занявшие третье и четвертое места, набрали разное число очков, причем отстали от лидеров, но обогнали аутсайдеров. Сколько очков набрал теннисист, занявший третье место? В теннисе за победу дают $1$ очко, за поражение — $0$ очков, а ничьих не бывает.

Источники: Лига открытий - 2018

Показать ответ и решение

У каждого из двух аутсайдеров должно быть минимум по одному очку, ибо один из них выиграл у другого личную встречу. Значит, теннисист, занявший четвертое место, набрал минимум $2$ очка, третье — минимум $3$ очка, а каждый из двух лидеров — минимум $4$ очка. Но и больше, чем по $4$ очка, лидеры набрать не могли, ибо один из них проиграл другому. Поэтому у третьего и четвертого теннисистов должно быть ровно $3$ и $2$ очка соответственно.

Ответ:

$3$

Ошибка.
Попробуйте повторить позже

Задача 59#33571Максимум баллов за задание: 7

В футбольном турнире участвовало $20$ команд, каждая сыграла с каждой ровно один матч. За победу даётся $3$ очка, за ничью — $1$ очко, за поражение — $0$ очков. В сумме команды набрали $554$ очка. Докажите, что найдутся $7$ команд, каждая из которых сыграла хотя бы один раз вничью.

Источники: КМО - 2017, первая задача второго дня, общая для 8-11 классов, автор Белов Д.А. по мотивам фольклора (cmo.adygmath.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Все команды, сыгравшие в ничью, играли их именно друг с другом. Таких команд по предположению не более 6, значит игр с ничьей не более 15. Что еще можно сказать о количестве очков?

Подсказка 3

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

Показать ответ и решение

Предположим, что $7$ команд, каждая из которых хотя бы раз сыграла вничью, не найдется. То есть команд, которые сыграли хотя бы раз вничью, не больше $6$ . Тогда ничейных матчей было не больше $6⋅5 2 = 15$ .

Матчей всего $20⋅19 2 = 190$ . Если матч закончился вничью, то в нём было разыграно $2$ очка, иначе – $3$ . Ничейных матчей не более $15$ , поэтому суммарно очков в турнире было набрано не менее $15 ⋅2 +(190 − 15)⋅3= 555$ .

По условию задачи команды в сумме набрали $554$ очка. Предположение о том, что команд, у которых был ничейный матч, меньше $7$ приводит к противоречию $554≥ 555$ . Поэтому хотя бы $7$ команд точно найдутся.

Ответ:

что и требовалось доказать

Ошибка.
Попробуйте повторить позже

Задача 60#68082Максимум баллов за задание: 7

Трое играют в настольный теннис, причём игрок, проигравший партию, уступает место игроку, не участвовавшему в ней. В итоге оказалось, что первый игрок сыграл $21$ партию, а второй $10.$ Сколько партий сыграл третий игрок?

Источники: Всесиб - 2017, 10.2(см. sesc.nsu.ru)

Показать ответ и решение

По условию первый игрок сыграл $21$ партию, поэтому всего было сыграно не менее $21$ партии. Из каждых двух партий подряд второй игрок хотя бы в одной должен участвовать, значит, партий было не более $2⋅10+1 =21.$ Следовательно, была сыграна всего $21$ партия, и второй игрок участвовал в каждой из них. В $10$ партиях он встречался с первым, а в оставшихся $11$ партиях — с третьим. Пример такого турнира: первый игрок встречается со вторым в партиях с чётными номерами, а с третьим – в партиях с нечётными номерами.

Ответ: 11

Критерии оценки

Если ответ угадан и приведѐн пример турнира: 1 балл.

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

Не приведѐн пример турнира: минус 1 балл.

Предыдущая подтема

Следующая подтема