Question

Прочитайте текст.
В групповой стадии финальной части Чемпионата Мира по футболу играет 32 команды, разделенные на 8 групп, по 4 команды в каждой группе. По итогам групповой стадии в плей-офф выходит ровно две команды из каждой группы.
В группе каждая команда играет с каждой ровно один раз. За победу команде дается 3 очка, за поражение - 0 очков. Допускается ничья, в этом случае каждая из игравших команд получает по 1 очку.

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

Answer 1

Пусть в группе играют команды A, B, C, D.

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

Команда А выиграла у команды В;

Команда В выиграла у команды С;

Команда С выиграла у команды А.

Тогда, имеем таблицу:

$\left[\begin{array}{ccccccc}A&\times&+&-&+&2-0-1&6\\B&-&\times&+&+&2-0-1&6\\C&+&-&\times&+&2-0-1&6\\D&-&-&-&\times&0-0-3&0\end{array}\right]$

Каждая из команд А, В, С имеет 2 победы, 0 ничьих и 1 поражение. Соответственно, каждая из них имеет по 6 очков.

Команда D имеет 0 побед, 0 ничьих и 3 поражения. Соответственно, она имеет 0 очков.

Учитывая, что в плей-офф выходят только две команды, то одна из команд А, В, С не сможет выйти из группы, имея при этом 6 очков (отбор будет производиться по дополнительным критериям, таким как разница мячей и т.п., в этой задаче эти критерии нас не интересуют).

Таким образом, имея 6 очков, команда может не выйти из группы.

Теперь докажем, что, имея 7 очков, команда гарантированно выйдет из группы.

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

Заметим, что максимальное количество очков, которое может быть разыграно в одном матче, равно 3 (в случае, если в игре кто-то победил). Также, заметим, что всего в группе проводится 6 игр.

Таким образом, максимальное количество очков, которое может быть разыграно в группе, равно 3·6=18. Но по предположению, суммарно у всех команд оказалось как минимум 21 очко. Значит, предположение неверно, и, набрав 7 очков, команда действительно выйдет из группы.

Ответ: 6 очков