Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела спбгу
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#80506

В однокруговом турнире по настольному теннису приняло участие 35 человек. По итогам турнира оказалось, что нет такой четверки игроков A,B,C,D  , что A  выиграл у B,B  — у C,C  — у D  , а D  — у A.  Каково наибольшее количество троек участников, одержавших во всех трех встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.

Показать ответ и решение

Пусть есть 2 тройки, которые пересекаются по ребру. Назовем их A,B,C  и A,B,D  . Тогда нуо A  выиграл у B  и C  выиграл у D  , то B  выиграл у C  и D  , а A  проиграл C  и D  . Тогда A  выиграл у B  , B  выиграл у C  , C  выиграл у D  , а D  выиграл у A  ?!

Пусть есть 2 тройки, которые пересекаются по вершине. Назовем их A,B,C  и C,D,E  . Тогда без ограничения общности C  выиграл у A  и D  и D  выиграл у A  , то A  выиграл у B  , B  выиграл у C  , D  выиграл у E  и E  выиграл у C  . Тогда A  выиграл у B  ,    B  выиграл у C  , C  выиграл у D  , а D  выиграл у A  ?!

Значит, тройки не пересекаются и из не более 11. Осталось показать, что 11 троек может быть. Давайте выделим 11 непересекающихся троек и еще двойку и пронумеруем их от 1 до 14. В каждой тройке у нас будет цикл, в двойке победа будет у любого, а между группами    i  и j  (где i⁄= j  ) победа будет у группы с большим номером. Тогда если появится запретная четверка, то заметим, что если обходить ее по кругу от проигравшего к победителю, то номер группы может только расти или не изменяться. Раз мы вернемся в конце в начальную вершину, то номер группы должен все время не изменяться, и значит, все 4 вершины лежат в одной группе?! Значит, запретных четверок в таком турнире не будет.

Ответ: 11

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!