?

Log in

задачка - Поклонник деепричастий [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: alexcohn
2003-09-10 01:23 pm
симметрия-шмиметрия, 1. f2 и белые с черными симметричны на горизонталях 1 и 3. А на второй пусть черные еще порыпаются...
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-09-10 01:30 pm
На 1.f2 чёрные отвечают 1..d1.
(Ответить) (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: avva
2003-09-10 08:44 am
Я выше уже написал, что выигрывает 1.f1.

Давайте играть. Я буду за чёрных. Отвечаю: 1.. f2.
(Ответить) (Parent) (Thread)
[User Picture]From: mz1313
2003-09-10 09:10 am
Понял ошибку. Значит так... Стратегия такая: следует заставить противника сравнять расстояния на двух рядах, после чего своим ходом тут же заткнуть третий. И дальше каждым ответом на ход противника опять уравнивать расстояния, выбирая наименьшее из двух. Чтобы этого достигнуть, нужно прийти к расстояниям (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), после чего белые проигрывают.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-09-10 09:12 am
Это уже лучше, хотя не совсем точно. Есть более общий и более простой принцип.
(Ответить) (Parent) (Thread)
[User Picture]From: urs
2003-09-10 10:01 pm
Правильного решения не знаю, но мое решение точно такое же
(Ответить) (Parent) (Thread)
[User Picture]From: mz1313
2003-09-10 11:26 pm
Понял ошибку. Значит так... Стратегия такая: следует заставить противника сравнять расстояния на двух рядах, после чего своим ходом тут же заткнуть третий. И дальше каждым ответом на ход противника опять уравнивать расстояния, выбирая наименьшее из двух. Чтобы этого достигнуть, нужно прийти к расстояниям (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), после чего белые проигрывают.
(Ответить) (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: denspb
2003-09-10 08:29 am
Выигрывает первый. Проигрышные (для противника) позиции:
a1, b3, c2, d6, f4, e8, h5, g11, k7, n10, s12, v13.
Первый может делать ходы на проигрышные позиции при любой игре противника.
С помощью листика в клеточку и highliter'а эта задачка решается за 3 минуты.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-09-10 08:42 am
Давайте играть. Я буду за чёрных. Начинайте.
(Ответить) (Parent) (Thread)
[User Picture]From: denspb
2003-09-10 11:20 pm

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

v13
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-09-10 08:49 pm
Угу, верно.
А трудная ее часть, и обалденно красивая, - дать удобное описание _всех_ проигрышных позиций.
(Ответить) (Parent) (Thread)
[User Picture]From: denspb
2003-09-11 12:37 am
У меня есть очень большое подозрение, что это выглядит так:
1) все позиции симметричные, поэтому имеет описывать только нижний треугольник.
2) координаты следующей позиции сдвинуты отностительно предыдущей либо на (+1, +2), либо на (+2, +3) (для квадратика 1000x1000 это выполняется).
3) запишем последовательность этих сдвигов, обозначив "1" первый вариант сдвига и "2" второй:
121221212212212122121221221212212212122121221221212212122122121....
4) Нету 2х единиц подряд. А теперь если выписать количество двоек между единицами, то получаем....
121221212212212.... ту же самую последовательность!
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-09-10 09:24 am
(исправляя очевидную ошибку)

Легко, нет? Идём по вертикалям, отмечая выигрышные поля для первого игрока. На первой вертикали это a2, a4, a6, a8, a10, a12. На второй - любое поле выигрышное, т.к. с любого можно вступить на a1,a3,a5... Значит, находясь на третьей, не имеет смысла ступать на вторую, точно проиграешь, поэтому можно двигаться только вниз, и выигрышные поля на ней: c2, c4, c6, c8... На четвёртой опять все выигрышные. Приходим к z, которая у нас 26-я буква ;), и поэтому ход z13-y13! выигрывает. Так?
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-09-10 08:47 pm
Авва, все же ферзь, а не король!
На первой вертикали все поля, кроме a1, для первого выигрышные.
(Ответить) (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: dimrub
2003-09-10 11:03 am

Re: P.S. shame on you!

Это не совсем ним, есть одно отличие, но оно действительно не принципиальное.
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2003-09-11 12:58 pm

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

Написанное буквально означает, что Анатолий узнал эту задачу от меня. Я бы даже сказал - посредством, не побоюсь этого ласкового слова, меня. Вас это по какой-то причине удивляет.. Знаете, люди общаются -- кто как может, передают друг другу информацию иногда..
(Ответить) (Parent) (Thread)
[User Picture]From: arbat
2003-09-11 05:59 pm

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


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

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

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2003-09-11 06:41 pm

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

Я знаю, конечно, игру Ним; просто не сразу связал. Однако к тому моменту, как я запостил задачу в своём журнале, я уже знал решение.
(Ответить) (Parent) (Thread)
[User Picture]From: arbat
2003-09-11 08:21 pm

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


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

(Ответить) (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)