Графы и турниры на Курчатове
Ошибка.
Попробуйте повторить позже
В школьном турнире по крестикам-ноликам участвовали 16 учеников, каждый сыграл с каждым ровно одну игру. За победу давалось 5 очков, за ничью — 2 очка, за поражение — 0 очков. После завершения турнира выяснилось, что суммарно все участники набрали 550 очков. Какое наибольшее количество участников могло ни разу не сыграть вничью в этом турнире?
Источники:
Подсказка 1
Посчитаем кол-во игр, их всего 120 штук. Понятно, что в каждой игре разыгрывалось либо 4, либо 5 очков. Можно ли выяснить, сколько тогда всего было ничьих?
Подсказка 2
Да! Просто решив маленькое уравнение, получаем что ничьих было ровно 50. Теперь подумайте, что если игроков, которые никогда не сыграли в ничью, было слишком много, то это плохо)
Подсказка 3
Например, можно считать, что x человек никогда не играли в ничью. Тогда ничейные партии могли пройти только среди оставшихся 16-x человек) Тут уже легко посчитать сколько вообще они могли сыграть между собой и понять, каким должен быть x!
Подсказка 4
Да, x должен быть не больше 5и! Осталось придумать пример, который можно получить как раз из наших оценок)
Всего за турнир было сыграно 
игр. В каждой игре разыгрывалось либо 5 очков (в случае победы-поражения), либо 4 очка (в
случае ничьей). Если бы все игры были сыграны вничью, то суммарное количество очков у всех участников равнялось бы 
что
на 70 меньше, чем реальная сумма очков всех участников. В случае не ничейной игры два её участника суммарно получают на 1 очко
больше, чем в случае ничейной игры. Это означает, что ровно 70 игр завершились победой одного из участников, а остальные 50 игр
закончились вничью.
Предположим, что хотя бы 6 участников ни разу не сыграли вничью. Тогда ничейные партии могли пройти только между оставшимися
10 участниками, а всего они между собой сыграли 
игр, что меньше 50. Противоречие. Следовательно, не более 5 участников ни
разу не сыграли вничью.
Нетрудно описать пример для 5 участников. Зафиксируем 11 участников, они сыграли между собой 
игр. Выберем любые 50
из этих игр, пусть они были сыграны вничью (ясно тогда, что каждый из зафиксированных 11 участников хотя бы раз сыграет вничью), а
все остальные игры турнира закончились победой любого из участников. Следовательно, 
человек ни разу не сыграли вничью.
Ясно, что все условия задачи выполняются.
