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