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