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