В первенстве по футболу участвует 20 команд, которые играют по разу друг с другом. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?
Решение. Будем рассматривать несыгранные игры. Условие означает, что несыгранные игры не образуют треугольников. Докажем индукцией по k, что для 2k команд наибольшее число несыгранных игр не больше
База индукции: (оценка очевидна).
Шаг индукции: Пусть доказано для k: докажем для Если несыгранных игр нет, то всё доказано. Иначе выделим произвольные команды A и B, не игравшие между собой. Заметим, что несыгранных игр с участием команд A или B не более (не считая игры между A и B), так как для любой команды C сыграна хотя бы одна из игр AC и BC. Теперь рассмотрим все команды, кроме A и B и применим предположение индукции — среди них не сыграно не более игр. Отсюда общее количество несыгранных игр не более что и требовалось доказать.
Подставляя получаем, что число несыгранных игр не более 100, а число всех возможных игр откуда число сыгранных игр не менее
Оценка достигается, если разбить команды на две равные группы, в каждой из которых провести все матчи, а между группами не проводить ни одного.
Ответ: 90 игр.
Общие критерии оценивания
По результатам проверки каждого задания выставляется одна из следующих оценок:
а) «+», «±» — задача скорее решена;
б) «∓», «−» — задача скорее не решена;
в) за задачу, к решению которой участник не приступал, ставится оценка «0».
При подведении итогов учитывается только количество в целом решенных задач - задач, за которые поставлена оценка «+» или «±».
Оценки по задачам имеются в таблице в личном кабинете участника. Оценки внутри работы и на титульном листе работы выставлены в процессе предварительной проверки и не являются основанием для апелляции.
Приведённые далее критерии описывают оценки продвижений и ошибок, встречающихся во многих работах. Поэтому они не подлежат изменению и могут быть использованы для апелляции только в случае, если вы укажете, что какое-то место в вашей работе, подходящее под один из этих критериев, оценено не в соответствии с ним.
Комментарий по оцениванию данной задачи
Приведен пример схемы турнира, при которой достигается верный ответ, но доказательство того, что меньше игр быть не могло, отсутствует или неполно — «∓».
Получен неверный ответ (за исключением арифметических ошибок) — «−».