Индукция в графах и теорема Турана
Ошибка.
Попробуйте повторить позже
16 команд провели турнир по хоккею, каждая команда сыграла с каждой по разу. За победу начислялось 2 очка, за ничью — 1 очко, за проигрыш очков не давалось. При этом каждые три команды в играх между собой набрали разное количество очков. Какое наибольшее число ничьих могло быть в этом турнире?
Источники:
Подсказка 1
Пупупу… давайте попробуем получить оценку сверху на количество ничьих! Для этого, попробуйте построить примеры для N=2, 3, 4 и 5. Причём примеры такие, в которых количество ничьих максимально!
Подсказка 2
Да, мы получили оценку на N²/4. Остаётся придумать как доказать, что эта формула работает для любого N!
Подсказка 3
Да, это утверждение мы будем доказывать по индукции! Для этого достаточно рассмотреть две команды, которые сыграли в ничью и подумать, как могли сыграть все другие команды с этими двумя!
Подсказка 4
Так, но мы только показали, что существует такая оценка сверху! Теперь нужно придумать пример такой, что в оценке сверху достигается равенство(пример должен быть для любого N)
Подсказка 5
Для построения примера, попробуйте посмотреть на маленькие N и воспользоваться идеей разбиения элементов от 1 до N на два непересекающихся множества. Также, возможно, Вам придётся строить пример в зависимости от четности N.
Решим задача для произвольного 
Докажем утверждение, известное в олимпиадных кругах как теорема Турана.
Оценка: Докажем по индукции, что число ничьих не превосходит 
База индукции: При 
это очевидно. При 
все три игры не могли закончиться вничью, иначе у всех команд было бы
одинаковое число очков.
Шаг индукции: Рассмотрим две команды 
и 
сыгравшие вничью. С каждой из остальных команд хотя бы одна из них сыграла не
вничью, иначе образуется запрещенная тройка команд. Значит, общее число ничьих в играх с участием этих двух команд не больше 
По предположению индукции в играх между остальными командами было не более 
ничьих. Следовательно, общее число ничьих не
превосходит 
Пример: Пронумеруем команды числами от 
до 
Пусть каждые две команды с номерами разной чётности сыграли вничью, а в
играх между командами с номерами одной чётности победила команда в меньшим номером. Если 
то 
команд имеют
нечётный номер и 
команда - чётный, поэтому количество ничьих равно 
При 
получаем по 
команд с номерами
каждой чётности и 
ничьих. В обоих случаях полученное число равно ![[ 2]
N4 .](/api/latex-service/v1/GetSession/127110/index-2671d4a25f33460511ed8f212426ff2e.svg)
При этом каждые три команды в играх между собой
набрали либо 0, 2 или 4 очка, если имеют номера одной чётности, либо 
очка, если две из них имеют номера одной чётности, а третья -
другой.
Замечание. Заметим, что идея примера приходит из двудольного графа, где разная чётность номеров отвечает разным компонентам.
Подставим 
и получим ответ.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
