Графы, турниры и игры на СПБГУ
Ошибка.
Попробуйте повторить позже
В однокруговом турнире по настольному теннису приняло участие 35 человек. По итогам турнира оказалось, что нет такой четверки игроков
, что 
выиграл у 
— у 
— у 
, а 
— у 
Каково наибольшее количество троек участников, одержавших во всех
трех встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.
Подсказка 1
Как из двух троек можно получить четвёрку?
Подсказка 2
У них должны быть 2 общих участника. Что тогда можно сказать о полученной четвёрке?
Подсказка 3
Докажите, что тройки не пересекаются, и получите оценку на их количество.
Пусть есть 
тройки, которые пересекаются по ребру. Назовем их 
и 
Тогда не умаляя общности 
выиграл у 
и 
выиграл у 
выиграл у 
и 
а 
проиграл 
и 
. Тогда 
выиграл у 
выиграл у 
выиграл у 
а 
выиграл у 
?!
Пусть есть 2 тройки, которые пересекаются по вершине. Назовем их 
и 
. Тогда без ограничения общности 
выиграл у
и 
и 
выиграл у 
выиграл у 
выиграл у 
, 
выиграл у 
и 
выиграл у 
Тогда 
выиграл у 
выиграл у 
выиграл у 
а 
выиграл у 
?!
Значит, тройки не пересекаются и их не более 11. Осталось показать, что 11 троек может быть. Давайте выделим 11 непересекающихся
троек и еще двойку и пронумеруем их от 1 до 14. В каждой тройке у нас будет цикл, в двойке победа будет у любого, а между группами 
и
(где 
победа будет у группы с большим номером. Тогда если появится запретная четверка, то заметим, что если обходить ее по
кругу от проигравшего к победителю, то номер группы может только расти или не изменяться. Раз мы вернемся в конце в начальную
вершину, то номер группы должен все время не изменяться, и значит, все 4 вершины лежат в одной группе?! Значит, запретных четверок в
таком турнире не будет.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
