Ошибка.
Попробуйте повторить позже
Будем говорить, что набор чисел сильнее набора чисел если среди всех неравенств вида количество верных неравенств не менее чем в раза превосходит количество неверных. Докажите, что не существует трех наборов таких, что сильнее сильнее сильнее
Подсказка 1
Нам дали факт о том, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных» и просят доказать, что какой-то факт не выполнен, скорее всего мы получим противоречие с тем, что какая-то величина будет одновременно больше и меньше какого-то числа или мы сможем показать, что она не меньше и не больше некоторой числа, а значит равна ему и такой случай уже намного проще разобрать.
Подсказка 2
Давайте теперь зафиксируем произвольную тройку (A_i, B_j, C_t) и распишем для неё условие, что A сильнее B, B сильнее C, C сильнее A. А сколько вообще может быть верных неравенств при таком условии? Может попробовать оценить сверху и снизу количество верных неравенств?
Подсказка 3
Действительно, количество верных неравенств не больше чем 2, мы показали это для произвольной тройки, а сколько всего троек? Теперь попробуем понять, как ограничить эту величину снизу. Мы не пользовались тем, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных». Как раз «не менее» намекает нам о том, что мы сможем оценить снизу.
Подсказка 4
Можно посмотреть на наборы A, B и поотвечать на вопросы. А сколько можно записать неравенств вида a_i > b_j? А сколько из них должны быть верными? А мы пользовались какими-либо особенностями множеств A и B или это можно сказать для любой пары множеств?
Подсказка 5
Ура, мы получили, что количество верных неравенств не меньше чего-то, но и не больше, а значит в точности равно этому числу. Это уже хорошее условие, но на самом деле мы знаем больше! Что должно выполняться, чтобы это равенство достигалось?
Подсказка 6
Верно, количество верных неравенств должно быть ровно в 2 раза больше количества неверных! Так как мы доказываем, что такого не бывает, то в какой-то из пар наборов количество верных больше, чем в 2 раза неверных, а для числа с каким свойством неравенство было бы выполнено для всех остальных чисел?
Подсказка 7
Верно, для наибольшего из всех чисел или для наименьшего, здесь мы пользовались принципом крайнего, который часто может встречаться в задачках, где что-то сравнивается. Вернёмся к условию, что A сильнее B, B сильнее C, C сильнее A, оно ведь тоже участвовало в оценке, тогда что должно быть верно, чтобы она достигалась? Как нам объединить это с прошлым фактом?
Подсказка 8
Давайте рассмотрим тройку с минимальный (для максимального тоже верно) числом из всех наборов, тогда одно из неравенств очевидно выполнено, а другое - нет. Что можно сказать про оставшееся, а сколько таких неравенств, где в тройке участвует минимальное (максимальное) число? А сколько должно должно быть верных неравенств в паре наборов?
Предположим противное. Пусть наборы
таковы, что сильнее сильнее сильнее Можно считать, что число наибольшее среди всех чисел этих трёх наборов. Для каждой тройки индексов посчитаем, сколько верных увтерждений имеется среди неравенств просуммируем эти числа по всем и обозначим полученную сумму через Тогда
поскольку всего имеется троек и в каждой тройке не больше двух верных неравенств. Далее заметим, что каждое неравенство присутствует в таких тройках, поэтому в сумме оно учтено раз. По предположению среди неравенств не меньше верных, поэтому вклад всех неравенств вида в сумму не меньше чем Аналогично вклад всех неравенств вида в сумму и вклад всех неравенств вида в сумму также не меньше чем Следовательно, суммарное количество верных неравенств не меньше чем
Сопоставляя это с неравенством заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности верных неравенств вида а в каждой тройке ровно два верных неравенства.
Рассмотрим теперь тройку чисел Среди неравенств должно быть ровно два верных. Поскольку — наибольшее число неравенство неверно, т.е. выолняется неравенство Значит, все неравенства вида верные и всего их штук. Но это противоречит тому, что их Стало быть, наше предположение неверно.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!