?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [сент. 10, 2003|04:17 pm]
Anatoly Vorobey
Хорошая задачка от ppetya:

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

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

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

Comments:
[User Picture]From: dimrub
2003-09-10 06:28 am
Это просто сим. Кажущееся отличие, заключаещаеся в том, что можно свою пешку удалять от вражеской (таким образом, как бы, увеличивая кол-во спичек в кучке, если говорить терминами сима) - несущественно, т.к. противник придвигается на столько же клеток, и позиция возвращается в исходную.
(Ответить) (Thread)
[User Picture]From: avva
2003-09-10 06:31 am

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

Я скрою пока наши комменты, чтобы дать людям ещё подумать, хорошо?
(Ответить) (Parent) (Thread)
[User Picture]From: lu_in_pampas
2003-09-10 06:30 am
Тот, после чьего хода окажется ситуация, что на каждой горизонтали пара пешек стоит рядом - выиграет. Потому что противник после этого сможет только отступать, а он в свою очередь будет наступать, сохраняя эту ситуацию.
Почему-то мне кажется, что первым ходом разумно передвинуть пешку с a1 на h1 и навсегда забыть про этот ряд, но, возможно я не права.
(Ответить) (Thread)
[User Picture]From: avva
2003-09-10 06:33 am
Нет, если Вы первым ходом подвините пешку с a1 до упора (g1, а не h1), тогда чёрные выиграют тонким ходом e2!, устанавливая симметрию ;)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: mz1313
2003-09-10 07:21 am
Выигрывает ход 1.f1!
(Ответить) (Thread)
[User Picture]From: pishi_chitai
2003-09-10 08:20 am
Сыграем? .-)
Черные - f2.
(Ответить) (Parent) (Thread)
[User Picture]From: mz1313
2003-09-10 07:36 am
Я выше уже написал, что выигрывает 1.f1. Забыл указать выигрывающую тактику после этого. Идея такая: белые вынуждают черных своим ходом "заткнуть" один из рядов (это несложно), после чего тут же становятся в "оппозицию" на двух остальных. Под оппозицией я в данном случае имею ввиду ситуацию, когда расстояние между белой и черной пешками на каждом из рядов одинаковое. Это чтобы не думать. На самом деле минимальное достаточное условие - это чтобы сумма расстояний на двух "незаткнутых" рядах была четной.
(Ответить) (Thread)
[User Picture]From: mz1313
2003-09-10 07:49 am
Уточнение. Нужна именно оппозиция.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-09-10 07:58 am

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

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

(Ответить) (Thread)
[User Picture]From: mz1313
2003-09-10 08:16 am
По-моему, и здесь выиграет тот, кто ходит первым. Правильный ход: 1.Y13. Каждым своим ходом он ставит ферзя на клетку с нечетным номером горизонтали и нечетным же номером вертикали. Y13 - это 25:13 (вертикаль : горизонталь).
(Ответить) (Parent) (Thread)
[User Picture]From: pishi_chitai
2003-09-10 08:21 am
Соображения.

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

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

Над стратегией надо ещё поразмыслить.
(Ответить) (Thread)
[User Picture]From: arbat
2003-09-10 09:48 am

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

(Ответить) (Thread)
[User Picture]From: arbat
2003-09-10 09:50 am

P.S. shame on you!

.


(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vt
2003-09-10 10:30 am
Кажется, белые выигрывают ходом 1.c1, и на симметричное 1...f1 2 f2!
(Ответить) (Thread)
[User Picture]From: avva
2003-09-10 01:24 pm
На 1.c1 чёрные отвечают 1...d3 и вскоре выигрывают.
(Ответить) (Parent) (Thread)
[User Picture]From: muchacho
2003-09-10 11:05 pm
Обозначим позицию как klm, где klm - число пустых клеток между двумя пешками в каждом ряду.
Положения пешек при этом неважны, потому что ход назад не может изменить позицию: противник всегда может пододвинуть свою пешку на такое же расстояние, восстановив позицию.
Очевидно, игрок выигрывает, если после его хода позиция: 000, т.к. в этом случае противник может двигать пешки только назад, что не меняет его позиции.
Из этого очевидно следует, что игрок также выигрывает, если после его хода позиция: 0nn (порядок неважен) - при этом ему достаточно после любого хода противника уменьшать максимальное расстояние до второго.
Из этого (неочевидно) следует, что игрок выигрывает, если после его хода позиция:
1(2n)(2n+1). Почему? Выигрышной является позиция 123, т.к. если противник увеличивает одно из расстояний, то игрок позицию восстанавливает, но рано или поздно противник вынужден будет уменьшить одно из расстояний, после чего игрок выставит выигрышную позицию 0nn.
Несложно показать дальнейшее по индукции.
Осталось выяснить, кто первый придёт к позиции 1(2n)(2n+1)
Начальная позиция: 246
Первый игрок может поменять позицию на 146, 236 или 245, не проиграв сразу.
Второй игрок выигрывает, выставив соответственно: 145, 231 или 145.
(Ответить) (Thread)