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