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