задачка

[avva]

Хорошая задачка от ppetya:

Отрезаем от шахматной доски первые три ряда, так что получается восемь столбцов, обозначенных a,b,c,d,e,f,g,h и три ряда, пронумерованных 1,2,3. Ставим три белые пешки на поля a1, b2, c3 и три чёрные — на поля h1, g2, f3. Игроки ходят поочерёдно, начинают белые. На каждом ходу игрок может взять одну из своих пешек и переместить её в любом направлении по горизонтали на любое количество шагов (на месте оставить не может), но при этом не может перепрыгивать через пешку противника или "съедать" её.

Когда игрок не может сделать ход, он прогрывает. Вопрос: кто выигрывает в начальном положении и какова выигрышная стратегия?

Если хотите решать сами, не заглядывайте в комменты, там наверняка появятся правильные ответы в какой-то момент.

Comments

[dimrub.livejournal.com]

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

[avva.livejournal.com]

В общем, верно, только не сим, а ним ;)

Я скрою пока наши комменты, чтобы дать людям ещё подумать, хорошо?

[lu-in-pampas.livejournal.com]

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

[avva.livejournal.com]

Нет, если Вы первым ходом подвините пешку с a1 до упора (g1, а не h1), тогда чёрные выиграют тонким ходом e2!, устанавливая симметрию ;)

[alexcohn.livejournal.com]

симметрия-шмиметрия, 1. f2 и белые с черными симметричны на горизонталях 1 и 3. А на второй пусть черные еще порыпаются...

[avva.livejournal.com]

На 1.f2 чёрные отвечают 1..d1.

[mz1313.livejournal.com]

Выигрывает ход 1.f1!

[pishi-chitai.livejournal.com]

Сыграем? .-)
Черные - f2.

[mz1313.livejournal.com]

Я выше уже написал, что выигрывает 1.f1. Забыл указать выигрывающую тактику после этого. Идея такая: белые вынуждают черных своим ходом "заткнуть" один из рядов (это несложно), после чего тут же становятся в "оппозицию" на двух остальных. Под оппозицией я в данном случае имею ввиду ситуацию, когда расстояние между белой и черной пешками на каждом из рядов одинаковое. Это чтобы не думать. На самом деле минимальное достаточное условие - это чтобы сумма расстояний на двух "незаткнутых" рядах была четной.

[mz1313.livejournal.com]

Уточнение. Нужна именно оппозиция.

[avva.livejournal.com]

Я выше уже написал, что выигрывает 1.f1.

Давайте играть. Я буду за чёрных. Отвечаю: 1.. f2.

[mz1313.livejournal.com]

Понял ошибку. Значит так... Стратегия такая: следует заставить противника сравнять расстояния на двух рядах, после чего своим ходом тут же заткнуть третий. И дальше каждым ответом на ход противника опять уравнивать расстояния, выбирая наименьшее из двух. Чтобы этого достигнуть, нужно прийти к расстояниям (1, 2, 3 - порядок произвольный) при ходе противника. Изначально у нас (2, 4, 6). Значит, варианты скоращений: 2->1 и 6->5. Стало быть выигрывает второй игрок - на 1)B1 следует 1)...E3. Или наоборот ( 1)C3-D3 H1-G1 ). Получается (1, 4, 5). Теперь белые своим ходом либо сравнивают расстояние на первом и втором рядах (по 4) на что черные затыкают третий, либо черные своим ответом смогут сделать (1, 2, 3), после чего белые проигрывают.

[avva.livejournal.com]

Это уже лучше, хотя не совсем точно. Есть более общий и более простой принцип.

[urs.livejournal.com]

Правильного решения не знаю, но мое решение точно такое же

[mz1313.livejournal.com]

Понял ошибку. Значит так... Стратегия такая: следует заставить противника сравнять расстояния на двух рядах, после чего своим ходом тут же заткнуть третий. И дальше каждым ответом на ход противника опять уравнивать расстояния, выбирая наименьшее из двух. Чтобы этого достигнуть, нужно прийти к расстояниям (1, 2, 3 - порядок произвольный) при ходе противника. Изначально у нас (2, 4, 6). Значит, варианты скоращений: 2->1 и 6->5. Стало быть выигрывает второй игрок - на 1)B1 следует 1)...E3. Или наоборот ( 1)C3-D3 H1-G1 ). Получается (1, 4, 5). Теперь белые своим ходом либо сравнивают расстояние на первом и втором рядах (по 4) на что черные затыкают третий, либо черные своим ответом смогут сделать (1, 2, 3), после чего белые проигрывают.

[flaass.livejournal.com]

Молчу, молчу...
А вправду интересно: решит ли кто? Я вот, увы, не успел: узнал решение раньше.

А еще: стоит ферзь на клетке z13. Двое по очереди придвигают его к a1 (разрешается только влево, вниз. или влево-вниз). Кто попал на a1 - выиграл.
(Эта труднее...)

[mz1313.livejournal.com]

По-моему, и здесь выиграет тот, кто ходит первым. Правильный ход: 1.Y13. Каждым своим ходом он ставит ферзя на клетку с нечетным номером горизонтали и нечетным же номером вертикали. Y13 - это 25:13 (вертикаль : горизонталь).

[denspb.livejournal.com]

Выигрывает первый. Проигрышные (для противника) позиции:
a1, b3, c2, d6, f4, e8, h5, g11, k7, n10, s12, v13.
Первый может делать ходы на проигрышные позиции при любой игре противника.
С помощью листика в клеточку и highliter'а эта задачка решается за 3 минуты.

[avva.livejournal.com]

Давайте играть. Я буду за чёрных. Начинайте.

Точно будем играть?

[denspb.livejournal.com]

v13

[flaass.livejournal.com]

Угу, верно.
А трудная ее часть, и обалденно красивая, - дать удобное описание _всех_ проигрышных позиций.

[denspb.livejournal.com]

У меня есть очень большое подозрение, что это выглядит так:
1) все позиции симметричные, поэтому имеет описывать только нижний треугольник.
2) координаты следующей позиции сдвинуты отностительно предыдущей либо на (+1, +2), либо на (+2, +3) (для квадратика 1000x1000 это выполняется).
3) запишем последовательность этих сдвигов, обозначив "1" первый вариант сдвига и "2" второй:
121221212212212122121221221212212212122121221221212212122122121....
4) Нету 2х единиц подряд. А теперь если выписать количество двоек между единицами, то получаем....
121221212212212.... ту же самую последовательность!

[avva.livejournal.com]

(исправляя очевидную ошибку)

Легко, нет? Идём по вертикалям, отмечая выигрышные поля для первого игрока. На первой вертикали это a2, a4, a6, a8, a10, a12. На второй - любое поле выигрышное, т.к. с любого можно вступить на a1,a3,a5... Значит, находясь на третьей, не имеет смысла ступать на вторую, точно проиграешь, поэтому можно двигаться только вниз, и выигрышные поля на ней: c2, c4, c6, c8... На четвёртой опять все выигрышные. Приходим к z, которая у нас 26-я буква ;), и поэтому ход z13-y13! выигрывает. Так?

[flaass.livejournal.com]

Авва, все же ферзь, а не король!
На первой вертикали все поля, кроме a1, для первого выигрышные.

[pishi-chitai.livejournal.com]

Соображения.

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

Т.е. если на двух любых горизонталях расстояния одинаковы - выиграет тот, чья очередь ходить. Он запрёт третью горизонталь.

Над стратегией надо ещё поразмыслить.

and the word you are looking for is "nim".

[arbat.livejournal.com]

ppetya?

http://www.wikipedia.org/wiki/Nim

P.S. shame on you!

[arbat.livejournal.com]

.

Re: P.S. shame on you!

[dimrub.livejournal.com]

Это не совсем ним, есть одно отличие, но оно действительно не принципиальное.

Re: and the word you are looking for is "nim".

[ppetya.livejournal.com]

Написанное буквально означает, что Анатолий узнал эту задачу от меня. Я бы даже сказал - посредством, не побоюсь этого ласкового слова, меня. Вас это по какой-то причине удивляет.. Знаете, люди общаются -- кто как может, передают друг другу информацию иногда..

Re: and the word you are looking for is "nim".

[arbat.livejournal.com]

Меня удивило, что Анатолий не знал эту задачу.
Все же - одна из базовых в теории игр.
Учитывая познания им обычно демонстрируемые - стыдно довольно-таки :-)

Я помню, как-то в Ситибанке услышал разговор из соседнего кубикла. Там, оказалось, неделю бьются над следующей задачей (не для игры, - по делу): имеется набор в сотни кредитных карточек. Надо его разделить на две части так, чтобы сумма долгов на карточках в каждой была примерно одинакова.

Re: and the word you are looking for is "nim".

[avva.livejournal.com]

Я знаю, конечно, игру Ним; просто не сразу связал. Однако к тому моменту, как я запостил задачу в своём журнале, я уже знал решение.

Re: and the word you are looking for is "nim".

[arbat.livejournal.com]

Excuse me, can a man gloat in peace without being interrupted here?

[vt.livejournal.com]

Кажется, белые выигрывают ходом 1.c1, и на симметричное 1...f1 2 f2!

[avva.livejournal.com]

На 1.c1 чёрные отвечают 1...d3 и вскоре выигрывают.

[muchacho.livejournal.com]

Обозначим позицию как klm, где klm - число пустых клеток между двумя пешками в каждом ряду.
Положения пешек при этом неважны, потому что ход назад не может изменить позицию: противник всегда может пододвинуть свою пешку на такое же расстояние, восстановив позицию.
Очевидно, игрок выигрывает, если после его хода позиция: 000, т.к. в этом случае противник может двигать пешки только назад, что не меняет его позиции.
Из этого очевидно следует, что игрок также выигрывает, если после его хода позиция: 0nn (порядок неважен) - при этом ему достаточно после любого хода противника уменьшать максимальное расстояние до второго.
Из этого (неочевидно) следует, что игрок выигрывает, если после его хода позиция:
1(2n)(2n+1). Почему? Выигрышной является позиция 123, т.к. если противник увеличивает одно из расстояний, то игрок позицию восстанавливает, но рано или поздно противник вынужден будет уменьшить одно из расстояний, после чего игрок выставит выигрышную позицию 0nn.
Несложно показать дальнейшее по индукции.
Осталось выяснить, кто первый придёт к позиции 1(2n)(2n+1)
Начальная позиция: 246
Первый игрок может поменять позицию на 146, 236 или 245, не проиграв сразу.
Второй игрок выигрывает, выставив соответственно: 145, 231 или 145.