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