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