Высшая проба 2016
Ошибка.
Попробуйте повторить позже
Дан куб, каждая грань которого — это клетчатое поле размером 
на 
клеток. В центре одной из граней стоит пешка. Данил и
Максим передвигают пешку по клеткам куба. Данил может ходить только на соседнюю по стороне клетку (разрешается переходить на
другую грань, если клетки соседние по стороне), а Максим может поставить пешку в любую клетку. Пешка красит за собой клетки. На
закрашенную клетку пешку двигать нельзя. Изначальная клетка (центр грани) закрашена. Данил ходит первым. Проигрывает тот, кто не
может сделать ход. Кто выиграет при правильной игре обоих?
Подсказка 1
Переформулируем немного задачу. Изначально куб пустой. Ходит первым Максим и ставит пешку в центр одной из граней.
Подсказка 2
Казалось бы, Максим может ставить на любую незакрашенную, а Данил всего лишь на соседние. Однако не тут-то было...
Подсказка 3
Побеждать будет Данил. Почему такая гипотеза должна появиться? Например, потому что всего клеток на кубе чётно, а первым ходит Максим, значит если все клетки заняты, то победит Данил (в силу чётности). А если бы мы предположили, что выигрывает Максим, то нам бы пришлось доказывать, что не бывает ситуаций, когда все клетки заняты (а это звучит стрёмно). На что же намекает замеченная чётность?
Подсказка 4
Верно! На парную стратегию, то есть ту, в которой у второго игрока всегда есть ответный ход. Какие существуют самые известные парный стратегии в плоских клетчатых задачах?
Подсказка 5
Точно! Это разбиение поля на доминошки (прямоугольники 1 на 2). То есть первый ходит в доминошку, а второй забирает оставшуюся клетку в доминошке. Итого, у второго всегда есть ход после первого. Сработает ли эта идея в нашей задаче?
Подсказка 6
Конечно, сработает. Стратегия остаётся той же. Однако с разбиением куба могут возникнуть трудности (всё-таки выход в пространство). И да, доминошки могут загибаться через рёбра.
Подсказка 7
Попробуйте построить пример следующим образом. Если куб ABCDA₁B₁C₁D₁, то попробуйте покрыть рёбра AB, B₁C₁, DD₁ доминошками (как бы облепить). Ну а дальше докрутить уже проще простого.
Приведём выигрышную стратегию для Данила. Число клеток на поверхности чётно (равно 
Разобьём всю поверхность куба
на доминошки; доминошки не пересекаются и покрывают весь куб. Легко видеть, что такие примеры есть. В начале хода Данила пешка
стоит в какой-то доминошке. Данил ходит во вторую клетку доминошки. Если Данил до этого действовал в соответствии с этой стратегией,
то вторая клетка доминошки не закрашена, и сделать в неё ход можно. Очевидно, что последний ход сделает Данил — хотя бы потому, что
он всегда может сделать ход.
Данил
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
