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