![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaХорошая задачка от ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
ppetya:
Отрезаем от шахматной доски первые три ряда, так что получается восемь столбцов, обозначенных a,b,c,d,e,f,g,h и три ряда, пронумерованных 1,2,3. Ставим три белые пешки на поля a1, b2, c3 и три чёрные — на поля h1, g2, f3. Игроки ходят поочерёдно, начинают белые. На каждом ходу игрок может взять одну из своих пешек и переместить её в любом направлении по горизонтали на любое количество шагов (на месте оставить не может), но при этом не может перепрыгивать через пешку противника или "съедать" её.
Когда игрок не может сделать ход, он прогрывает. Вопрос: кто выигрывает в начальном положении и какова выигрышная стратегия?
Если хотите решать сами, не заглядывайте в комменты, там наверняка появятся правильные ответы в какой-то момент.
ppetya:Отрезаем от шахматной доски первые три ряда, так что получается восемь столбцов, обозначенных a,b,c,d,e,f,g,h и три ряда, пронумерованных 1,2,3. Ставим три белые пешки на поля a1, b2, c3 и три чёрные — на поля h1, g2, f3. Игроки ходят поочерёдно, начинают белые. На каждом ходу игрок может взять одну из своих пешек и переместить её в любом направлении по горизонтали на любое количество шагов (на месте оставить не может), но при этом не может перепрыгивать через пешку противника или "съедать" её.
Когда игрок не может сделать ход, он прогрывает. Вопрос: кто выигрывает в начальном положении и какова выигрышная стратегия?
Если хотите решать сами, не заглядывайте в комменты, там наверняка появятся правильные ответы в какой-то момент.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-09-10 06:28 am (UTC)no subject
Date: 2003-09-10 06:30 am (UTC)Почему-то мне кажется, что первым ходом разумно передвинуть пешку с a1 на h1 и навсегда забыть про этот ряд, но, возможно я не права.
no subject
Я скрою пока наши комменты, чтобы дать людям ещё подумать, хорошо?
no subject
Date: 2003-09-10 06:33 am (UTC)no subject
Date: 2003-09-10 07:21 am (UTC)no subject
Date: 2003-09-10 07:36 am (UTC)no subject
Date: 2003-09-10 07:49 am (UTC)no subject
А вправду интересно: решит ли кто? Я вот, увы, не успел: узнал решение раньше.
А еще: стоит ферзь на клетке z13. Двое по очереди придвигают его к a1 (разрешается только влево, вниз. или влево-вниз). Кто попал на a1 - выиграл.
(Эта труднее...)
no subject
Date: 2003-09-10 08:16 am (UTC)no subject
Date: 2003-09-10 08:20 am (UTC)Черные - f2.
no subject
Date: 2003-09-10 08:21 am (UTC)На двух горизонталях проигрывает тот, кто при одинаковом расстоянии между пешками будет вынужден сделать первый ход.
Т.е. если на двух любых горизонталях расстояния одинаковы - выиграет тот, чья очередь ходить. Он запрёт третью горизонталь.
Над стратегией надо ещё поразмыслить.
no subject
Date: 2003-09-10 08:29 am (UTC)a1, b3, c2, d6, f4, e8, h5, g11, k7, n10, s12, v13.
Первый может делать ходы на проигрышные позиции при любой игре противника.
С помощью листика в клеточку и highliter'а эта задачка решается за 3 минуты.
no subject
Date: 2003-09-10 08:42 am (UTC)no subject
Date: 2003-09-10 08:44 am (UTC)Давайте играть. Я буду за чёрных. Отвечаю: 1.. f2.
no subject
Date: 2003-09-10 09:10 am (UTC)no subject
Date: 2003-09-10 09:12 am (UTC)no subject
Date: 2003-09-10 09:24 am (UTC)Легко, нет? Идём по вертикалям, отмечая выигрышные поля для первого игрока. На первой вертикали это a2, a4, a6, a8, a10, a12. На второй - любое поле выигрышное, т.к. с любого можно вступить на a1,a3,a5... Значит, находясь на третьей, не имеет смысла ступать на вторую, точно проиграешь, поэтому можно двигаться только вниз, и выигрышные поля на ней: c2, c4, c6, c8... На четвёртой опять все выигрышные. Приходим к z, которая у нас 26-я буква ;), и поэтому ход z13-y13! выигрывает. Так?
and the word you are looking for is "nim".
Date: 2003-09-10 09:48 am (UTC)http://www.wikipedia.org/wiki/Nim
P.S. shame on you!
no subject
Date: 2003-09-10 10:30 am (UTC)Re: P.S. shame on you!
Date: 2003-09-10 11:03 am (UTC)no subject
Date: 2003-09-10 01:23 pm (UTC)no subject
Date: 2003-09-10 01:24 pm (UTC)no subject
Date: 2003-09-10 01:30 pm (UTC)no subject
Date: 2003-09-10 08:47 pm (UTC)На первой вертикали все поля, кроме a1, для первого выигрышные.
no subject
Date: 2003-09-10 08:49 pm (UTC)А трудная ее часть, и обалденно красивая, - дать удобное описание _всех_ проигрышных позиций.
no subject
Date: 2003-09-10 10:01 pm (UTC)no subject
Date: 2003-09-10 11:05 pm (UTC)Положения пешек при этом неважны, потому что ход назад не может изменить позицию: противник всегда может пододвинуть свою пешку на такое же расстояние, восстановив позицию.
Очевидно, игрок выигрывает, если после его хода позиция: 000, т.к. в этом случае противник может двигать пешки только назад, что не меняет его позиции.
Из этого очевидно следует, что игрок также выигрывает, если после его хода позиция: 0nn (порядок неважен) - при этом ему достаточно после любого хода противника уменьшать максимальное расстояние до второго.
Из этого (неочевидно) следует, что игрок выигрывает, если после его хода позиция:
1(2n)(2n+1). Почему? Выигрышной является позиция 123, т.к. если противник увеличивает одно из расстояний, то игрок позицию восстанавливает, но рано или поздно противник вынужден будет уменьшить одно из расстояний, после чего игрок выставит выигрышную позицию 0nn.
Несложно показать дальнейшее по индукции.
Осталось выяснить, кто первый придёт к позиции 1(2n)(2n+1)
Начальная позиция: 246
Первый игрок может поменять позицию на 146, 236 или 245, не проиграв сразу.
Второй игрок выигрывает, выставив соответственно: 145, 231 или 145.
Точно будем играть?
Date: 2003-09-10 11:20 pm (UTC)no subject
Date: 2003-09-10 11:26 pm (UTC)no subject
Date: 2003-09-11 12:37 am (UTC)1) все позиции симметричные, поэтому имеет описывать только нижний треугольник.
2) координаты следующей позиции сдвинуты отностительно предыдущей либо на (+1, +2), либо на (+2, +3) (для квадратика 1000x1000 это выполняется).
3) запишем последовательность этих сдвигов, обозначив "1" первый вариант сдвига и "2" второй:
121221212212212122121221221212212212122121221221212212122122121....
4) Нету 2х единиц подряд. А теперь если выписать количество двоек между единицами, то получаем....
121221212212212.... ту же самую последовательность!
Re: and the word you are looking for is "nim".
Re: and the word you are looking for is "nim".
Date: 2003-09-11 05:59 pm (UTC)Меня удивило, что Анатолий не знал эту задачу.
Все же - одна из базовых в теории игр.
Учитывая познания им обычно демонстрируемые - стыдно довольно-таки :-)
Я помню, как-то в Ситибанке услышал разговор из соседнего кубикла. Там, оказалось, неделю бьются над следующей задачей (не для игры, - по делу): имеется набор в сотни кредитных карточек. Надо его разделить на две части так, чтобы сумма долгов на карточках в каждой была примерно одинакова.
Re: and the word you are looking for is "nim".
Date: 2003-09-11 06:41 pm (UTC)Re: and the word you are looking for is "nim".
Date: 2003-09-11 08:21 pm (UTC)Excuse me, can a man gloat in peace without being interrupted here?