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