?

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 ]

задачка [окт. 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: (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: rowaasr13
2005-10-06 05:51 pm
По-идее (задача о возможности обхода всей доски конём), проиграть должен первый, т.к. 64-й ход будет за вторым. Но так как первый может обломать это решение, выбрав клетку для начала обхода, то выиграет всё-таки он. Так?
(Ответить) (Thread)
[User Picture]From: avva
2005-10-06 05:52 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) (Развернуть)
[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)
[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: 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)