Question

В турнире по игре Dota участвовало 8 команд, которые в каждом туре разбивались на пары. Организаторы (для экономии средств) решили закончить турнир в тот момент, когда все участники наберут разное количество очков. За какое наименьшее число туров может закончиться такой турнир (победа - 1, поражение - 0, ничьих не бывает)?

Answer 1

В каждом туре проходит 4 игры и разыгрывается 4 очка (так как 4 пары команд).

Предположим, что одна команда будет побеждать в каждом туре. Тогда минимально возможное количество очков, набранных этой командой, при котором у всех команд будет разное количество очков, будет равно 7. Тогда у остальных команд будет 0, 1, 2, 3, 4, 5 и 6 очков. К этому моменту будет разыграно 4·7 = 28 очков, и сумма очков всех команд будет 0+1+2+3+4+5+6+7 = 28.

Ответ: 7 - наименьшее число туров, за которое может закончиться такой турнир.

Answer 2

Чтобы закончить турнир в наименьшем числе туров, необходимо учесть, что каждая пара команд играет друг против друга в каждом туре. Таким образом, если одна команда выигрывает, она получает 1 очко, а другая команда получает 0 очков.

Давайте рассмотрим ситуацию, когда 8 команд разбиваются на 4 пары:

Тур 1:

• Пара 1: Команда A vs. Команда B
• Пара 2: Команда C vs. Команда D
• Пара 3: Команда E vs. Команда F
• Пара 4: Команда G vs. Команда H

После этого тура, у нас будут команды, набравшие 1 очко (победители пар) и команды, набравшие 0 очков (проигравшие пары). Ни одна из команд не набрала разное количество очков.

Чтобы достичь цели, нам нужно убедиться, что в каждой паре обе команды выигрывают, то есть обе получают 1 очко. Это возможно, если все команды разбиты на две пары следующим образом:

Тур 2:

• Пара 1: Победители пары 1 vs. Победители пары 2
• Пара 2: Победители пары 3 vs. Победители пары 4

Теперь после второго тура у нас будет 4 команды с 2 очками и 4 команды с 0 очками. Все команды набрали разное количество очков, и турнир может закончиться наименьшим числом туров, равным 2.

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