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