Связность и связные подграфы (клики)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На доску выписали 777 попарно различных комплексных чисел. Оказалось, что можно ровно 760 способами выбрать два числа 
и 
записанных на доске, так, чтобы выполнялось равенство
Способы, которые отличаются перестановкой чисел, считаются одинаковыми. Докажите, что можно выбрать такие два числа 
и 
записанных на доске, что
Источники:
Подсказка 1:
Для начала стоит переписать условие в более удобном виде. На что может намекать сумма квадратов и удвоенное произведение по разные стороны от знака равенства?
Подсказка 2:
Верно! На квадрат разности. Имеем (a − b)² = −1, то есть a − b = ±i. Аналогично преобразуем выражение, которое нужно доказать: (с − d)² = −45. Итого, нужно найти пару с разницей 45i. Что это означает?
Подсказка 3:
Нужно найти 46 "подряд идущих" чисел с разницей в i. Формально, мы хотим найти числа a₁, a₂, ..., a₄₆ с разницей ровно i между соседними. Тогда a₁ и a₄₆ будут являться искомой парой. В подобных задачах бывает полезно ввести граф.
Подсказка 4:
Разумеется, вершины — числа, ребро проводим, если разница между числами равна i. Хотим найти путь длины 46. Какие замечания можно сделать про этот граф?
Подсказка 5:
Осознайте, что в нём нет циклов, а также степень каждой вершины не более двух. Что же это означает?
Подсказка 6:
Граф представляет собой набор непересекающихся простых путей (так называемых бамбуков). Докажите это самостоятельно. Каждый такой путь — отдельная компонента связности, являющаяся деревом. Вершин в графе 777, рёбер — 760. Какой вывод из этих фактов можно сделать?
Подсказка 7:
В графе ровно 17 компонент связности (докажите это), то есть 17 путей, общая длина которых 760. Дело за малым — докажите, что путь длины хотя бы 45 найдется. Успехов!
Заметим, что условие 
равносильно тому, что
или же 
Рассмотрим граф, вершины которого — записанные на доску числа, а ребро проводится между двумя числами,
которые отличаются на 
Согласно условию задачи, в таком графе ровно 760 рёбер. Каждая компонента связности этого
графа представляет собой путь и состоит из вершин-чисел вида 
…, 
Предположим, что в
этом графе 
компонент связности. Тогда в нём 
рёбер, поэтому 
Поскольку 
то в
какой-то компоненте связности хотя бы 46 вершин, поэтому какие-то две из этих вершин — это числа 
и 
Тогда
следовательно,
что и требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
