Дана доска а) 8 × 8, б) 2018 × 2018. В одной из двух центральных клеток верхнего ряда стоит слон. Разрешается ходить им по диагонали вниз на любое количество клеток. Проигрывает тот, кто не может сделать ход.

задан 13 Мар '18 20:49

10|600 символов нужно символов осталось
3

Дальше я буду доказывать, что если доска имеет размеры $%(4k+2) \times (4k+2)$%, то выиграшная стратегия есть у начинающего игрока. Если же размеры доски $%4k \times 4k$%, то выиграшная стратегия у второго игрока. Верхние углы доски обозначим А и В, а точку пересечения ее диагоналей - Р. Игроки могут ходить только внутри треугольника АВР (вишел на его сторону или из него - проиграл). Если доска имеет размеры $%(4k+2) \times (4k+2)$%, то расстояние от центральной клетки до одной диагонали доски равно $%k$% маленьких диагоналей (диагоналей малых клеток), а до второй - $%k-1$%. Если доска имеет размеры $%4k \times 4k$%, то расстояние от центральной клетки до обеих диагоналей доски равно $%k-1$%. Если доску развернуть на угол $%45^{\circ}$%, то увидим, что игроки ходят по сторонам прямоугольника $%k \times (k-1)$% (во втором случае - по сторонам квадрата $%(k-1) \times (k-1)$%). Причем они могут ходить только вниз или вправо, а начинает первый с верхней левой вершины прямоугольника. В случае прямоугольника $%k \times (k-1)$% выиграшная стратегия первого состоит в том, чтобы всегда после своего хода оставлять квадрат некого размера $%n \times n$% , по которому сможет ходить второй. В таком случае рано или поздно второму останется квадрат $%0 \times 0$% и он проиграет. Легко показать, что начинающий сможет так ходить - первый его ход на одну клетку (второму остается квадрат $%(k-1) \times (k-1)$%) . А дальше, если второй походил на некоторое число клеток, то первому надо походить на тоже самое число клеток, но в перпендикулярном направлении. Вот и все. В случае же квадрата $%(k-1) \times (k-1)$% первый и второй меняются местами.

ссылка

отвечен 14 Мар '18 19:02

10|600 символов нужно символов осталось
1

Напишу на всякий случай своё решение -- оно давно готово, но не было времени разместить.

Анализируем игру с конца. Когда слон на нижней горизонтали, позиция проиграна для того, кто в ней начинает. Эти клетки раскрасим в красный цвет. Если с какой-то клетки есть ход слоном на красную, то такую клетку раскрашиваем синим -- это значит, что она выиграна для начинающего в такой позиции.

Преимущество такого подхода в том, что анализ происходит автоматически: если клетка ещё не раскрашена, и с неё есть ход на красную, то мы можем противнику отдать проигранную для него позицию, то есть сами выигрываем. Такую клетку делаем синей. Если не можем, то есть любой ход нас ведёт в синюю клетку, то позиция нами проиграна, и она делается красной.

В обоих пунктах задачи мы в синий цвет раскрашиваем примерно 3/4 квадрата: обе диагонали, и то, что ниже хотя бы одной из них. Не считая, конечно, нижней горизонтали. Особую роль далее будет играть столбец посередине из двух соседних вертикалей. У доски чётного размера имеется "центр" в виде квадрата 2x2. Он уже раскрашен синим. Две клетки выше этого центра должны быть красными по построению. От них мы идём вверх по диагоналям, и эти клетки делаем синими. В частности, две клетки над двумя красными станут синими, а две клетки над ними -- снова красными. И так пока мы не дойдём до верхнего края.

Для доски 8x8 пары красных клеток будет в середине на горизонталях с номерами 6 и 8, считая снизу. Вверху обе центральные клетки красные. Начинающий проигрывает. Для доски 2018x2018 выше "центра" имеется 1008 горизонталей. Красные клетки на них располагаются через одну, и легко видеть, что в самом верху мы получим две синие. Здесь начинающий выигрывает при правильной игре. Стратегия проста: ставить слона на одну из красных клеток.

ссылка

отвечен 14 Мар '18 22:22

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×251

задан
13 Мар '18 20:49

показан
363 раза

обновлен
14 Мар '18 22:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru