?

Log in

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

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

Links
[Links:| English-language weblog ]

задачка [окт. 6, 2005|08:14 pm]
Anatoly Vorobey
Отличная задачка от botev'а.

Двое играют в следующую игру. Первый игрок ставит коня на шахматную доску, второй им ходит, потом первый им ходит, потом второй и так далее. Проигрывает тот, кто наступит на клетку, на которой конь уже был. Кто выигрывает при правильной игре?


(он обещает, что в комментах правильные ответы скрыты)

Пришлось немного подумать, но разобрался. Очень милая.

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

Comments:
From: kvasimodo
2005-10-06 05:28 pm
Если считать, что оба игрока знают о решении задачи "как обойти шахматным конем всю доску", то выигрывает второй.
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 05:29 pm
Можно предполагать, что они знают всё, что угодно, но докажите, если так считаете.
(Ответить) (Parent) (Thread)
From: kvasimodo
2005-10-06 05:36 pm
Ну, если оба знают, как обойти конем всю доску, то при условии, что они к этому и стемятся, у второго игрока остается 63 клетки. То есть, он начинает и заканчивает.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-10-06 05:37 pm
Они не стремятся к тому, чтобы обойти всю доску. Они стремятся к тому, чтобы выиграть, и для этого им вовсе необязательно, возможно, играть так, чтобы обойти всю доску.
(Ответить) (Parent) (Thread)
From: kvasimodo
2005-10-06 05:40 pm
Гм. А стартовое положение коня не имеет значения?
Первый ставит его куда угодно?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-10-06 05:40 pm
Не "куда угодно", а "куда хочет". Он стремится выиграть, как и второй.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2005-10-06 05:37 pm
Если предположить что "при правильной игре" означает, что игроки планомерно обойдут все без исключения клетки, то выиграет неизбежно 2-й.

Ибо именно он в итоге поставит коня на 64-ю, последнюю, клетку. (на 1-ю его в самом начале поставит 1-й)
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 05:38 pm
"При правильной игре" означает "максимизируя свои шансы на выигрыш". То, что это означает планомерно обходить все без исключения клетки, ни из чего не следует.
(Ответить) (Parent) (Thread)
[User Picture]From: andrew_voland
2005-10-06 05:41 pm
"При правильной игре" означает "максимизируя свои шансы на выигрыш"
При этом я исхожу из предположения, что действуя таким образом, каждый из игроков в итоге находит следующий ход.

Видимо, это преположение неверно. Беим искать другие решения.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-10-06 05:42 pm
Может, верно, может, неверно, но как минимум не доказано ;) если вы хотите его использовать, придётся вначале доказать.
(Ответить) (Parent) (Thread)
[User Picture]From: andrew_voland
2005-10-06 05:38 pm
Сорри, выше был я.
(Ответить) (Parent) (Thread)
[User Picture]From: rowaasr13
2005-10-06 05:51 pm
По-идее (задача о возможности обхода всей доски конём), проиграть должен первый, т.к. 64-й ход будет за вторым. Но так как первый может обломать это решение, выбрав клетку для начала обхода, то выиграет всё-таки он. Так?
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 05:52 pm
Нет ;) не из чего не следует, что они будут играть все 64 хода.
(Ответить) (Parent) (Thread)
[User Picture]From: rowaasr13
2005-10-06 05:53 pm
Ну я про то и говорю. Первый обламывает своим начальным выбором это решение и выигрывает.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-10-06 05:56 pm
Нет, неправильно ;) всё равно ни из чего не следует, что если бы он "обламывал", их оптимальным решением было бы идти все 64 поля.
Не говоря уж о том, что полный обход доски существует начиная с любого поля.
(Ответить) (Parent) (Thread)
From: justsoul
2005-10-06 06:07 pm

На вскидку

1ый выиграет. Ставя коня в угол и "прижимая" его каждым своим ходом к краю.
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 06:08 pm
В принципе, это представляется разумной стратегией. Но задачу нужно решить, дав строгое доказательство.
(Ответить) (Parent) (Thread)
From: justsoul
2005-10-06 07:31 pm
Все оказалось сложнее. Такая стратегия не работает. Пока вариантов больше нет=)
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2005-10-06 07:11 pm

Re: На вскидку

Может, это было бы неплохой стратегией... если бы было возможно. Второй за 3 хода выходит в центр доски.
(Ответить) (Parent) (Thread)
From: justsoul
2005-10-06 07:30 pm

Re: На вскидку

Это вы погорячились.
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2005-10-06 08:44 pm

Re: На вскидку

Да нет, вроде. Если хотите - сыграем :)
(Ответить) (Parent) (Thread)
[User Picture]From: bengoro
2005-10-06 06:59 pm

э.. женская логика молвит что:

первый. количество клеток четное, на последнюю "свободную" встанет второй, а потому первый проигрывает.
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 07:00 pm
Нет, это неверная логика ;) см. комментарии выше.
(Ответить) (Parent) (Thread)
[User Picture]From: botev
2005-10-06 07:05 pm
я там не совсем правильно, видимо, сформулировал. в явном виде стратегию привести можете? она несложная и довольно красивая, я, собственно, только из-за неё задачку и постил.
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 07:11 pm
Ну извините. Я доказал неконструктивно, но доказал ;)

Насчёт стратегии подумаю сейчас.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2005-10-06 08:21 pm
На самом деле стратегии две. Свой ответ не даю, так как знал ответ на похожую задачу.
(Ответить) (Parent) (Thread)
[User Picture]From: botev
2005-10-06 08:33 pm
я тоже две знаю
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2005-10-07 08:17 am
Да, я был неправ. Нашёл стратегию.
(Ответить) (Parent) (Thread)
[User Picture]From: relf
2005-10-07 02:47 am
Второй всегда выигрывает. Ему достаточно зафиксировать в голове обход конем всей доски, начиная с поля, на которое поставил коня первый игрок, и делать всегда ходы из этого обхода.
(Ответить) (Thread)
[User Picture]From: dimrub
2005-10-07 10:09 am
Но кто сказал, что первый тоже будет делать ходы из этого обхода?
(Ответить) (Parent) (Thread)
[User Picture]From: relf
2005-10-07 10:49 am
первый делает любые ходы. а вот второму главное придерживаться ходов из выбранного обхода.
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2005-10-07 12:00 pm
Кто сказал, что на любой ход первого найдется полный обход?
(Ответить) (Parent) (Thread)
[User Picture]From: relf
2005-10-07 12:27 pm
вроде бы это известный факт. алгоритм даже именитый есть.
но можно воспользоваться и совсем произвольным обходом. главное, первый ход в нужную сторону сделать - он должен быть нечетным по счету в выбранном обходе
(Ответить) (Parent) (Thread)
[User Picture]From: maccolit
2005-10-07 05:02 am
из общих соображений выигрывает второй
потому что перед ним нечетное число клеток
следовательно последняя незанятая клетка - его
(Ответить) (Thread)
[User Picture]From: vdots
2005-10-07 08:26 am
Выигрывает второй. Пусть он мысленно разобьёт доску на 32 непересекающиеся пары клеток так, чтобы в каждой паре клетки были связаны ходом коня (это, очевидно, возможно). На первом ходе он должен пойти на клетку, находящуюся в паре к той, на которой конь стоит изначально. Следующим ходом первый перемещает коня на клетку, парная к которой свободна (потому что единственная использовавшаяся пара израсходована полностью), и потому второй может сделать ход на соответствующую клетку. Продолжая в том же духе, второй сможет сделать ход после каждого хода первого, что и требовалось.
(Ответить) (Thread)
[User Picture]From: avva
2005-10-07 09:02 am
Ага, верно.
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2005-10-07 09:29 am
Пусть x(0),x(1),...,x(64)=x(0) циклический обход доски конём (где-то я читала в детстве, что такой существует ;-) Тогда второй игрок выигрывает, всегда ходя с x(i) на x(i+1), так как ясно, что x(i+1) ещё не использовалась — вторым потому, что он так ходит, а первым потому, что он вообще ходит по клеткам другого цвета. Ну как, правильное решение, или опять лажа как в той задаче, где я не того коня поставила на место короля?
(Ответить) (Thread)
[User Picture]From: avva
2005-10-07 11:50 am
Нет, это правильно.
(Ответить) (Parent) (Thread)