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