№19. Задачи на олимпиадные темы

Турниры

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

Осваивайте новые концепции ежедневно

Вдумывайтесь в теоретические материалы

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

Подтемы раздела: №19. Задачи на олимпиадные темы

Теоретическая справка

#579

Однокруговой турнир — турнир, в котором каждый участник сыграл с каждым ровно по одному разу.

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

Пусть состоялся однокруговой турнир, в котором за победу начислялось 2 очка, за поражение — 0, а за ничью — 1 очко. В нем участвовало 5 команд.

Найдем общее количество игр на турнире. Всего на турнире 5 команд. Турнир был однокруговой, то есть каждая команда сыграла с каждой. Значит, любая команда сыграла ровно 4 игры, так как сама с собой команда играть не может. Таким образом, мы получили $5⋅4= 20$ игр. Но это еще не всё.

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

5⋅4= 10 игр. 2

Правильность подсчетов легко проверить, нарисовав картинку турнира:

$12345$

Наши рассуждения не зависели от количества команд, поэтому можем написать формулу количества игр в однокруговом турнире, в котором участвовали $n$ команд. В таком турнире каждая команда сыграла $n− 1$ игру, поэтому игр всего в турнире было

n⋅(n−-1). 2

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

Посмотрим на команду, которая набрала наибольшее количество очков. В нашем случает она сыграла 4 игры, значит, выиграла не более четырех игр. Тогда и набрать она могла не более $4⋅2= 8$ турнирных очков.

А какое общее количество турнирых очков в сумме набрали все команды?

Исходя из описания турнира, мы можем понять, что в каждой игре разыгрывалось по 2 очка. Игр всего было 10, значит, общее количество очков равно $10⋅2 = 20.$

Важно! Не всегда бывает так, что сумма очков, разыгранных в партии, не зависит от результата матча. Например, если за ничью дают по 1 очку, за победу — 3 очка, а за поражение — 0 очков, то чтобы посчитать общее количество очков, нам нужно знать количество ничьих.

Наложим на наш пример дополнительное условие: все команды набрали различное количество очков. Тогда мы можем оценить максимальное количество очков проигравшей команды.

Пусть команда, набравшая наименьшее количество очков, набрала хотя бы 3 очка. Тогда следующая по количеству очков команда набрала хотя бы 4, следующая — хотя бы 5 и так далее. Получаем, что общее количество очков не меньше чем

3 +4 +5 +6 +7 = 25> 20.

Такого быть не могло, так как в турнире разыгрывалось всего 20 очков. Тогда пусть команда, набравшая наименьшее количество очков, набрала хотя бы 2 очка. Значит, общее количество очков не меньше чем

2 +3 +4 +5 +6 = 20.

Теперь противоречия нет, значит, команда, набравшая наименьшее количество очков, набрала не более 2 очков.

Сейчас может показаться, что мы ответили на вопрос: «Какое наибольшее количество очков может быть у команды, которая набрала наименьшее количество очков?» Заметим, что мы еще не доказали, что 2 — наибольшее количество очков. Мы показали, что теоретически такое возможно, но на практике может оказаться, что комбинации игр, в которой такая команда набирает 2 очка, нет. Чтобы окончательно ответить на этот вопрос, нужно привести пример: турнирную таблицу или другое описание результатов матчей, в которых проигравшая команда набрала ровно 2 очка.

Приведем такой пример — турнирую таблицу:


	1	2	3	4	5	Итог

1		0	2	2	2	6

2	2		0	1	2	5

3	0	2		0	2	4

4	0	1	2		0	3

5	0	0	0	2		2

Предыдущая справка

Следующая справка