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