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