задачка

[avva]

Отличная задачка от botev'а.

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


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

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

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

Comments

[kvasimodo.livejournal.com]

Если считать, что оба игрока знают о решении задачи "как обойти шахматным конем всю доску", то выигрывает второй.

[avva.livejournal.com]

Можно предполагать, что они знают всё, что угодно, но докажите, если так считаете.

[kvasimodo.livejournal.com]

Ну, если оба знают, как обойти конем всю доску, то при условии, что они к этому и стемятся, у второго игрока остается 63 клетки. То есть, он начинает и заканчивает.

[(Anonymous)]

Если предположить что "при правильной игре" означает, что игроки планомерно обойдут все без исключения клетки, то выиграет неизбежно 2-й.

Ибо именно он в итоге поставит коня на 64-ю, последнюю, клетку. (на 1-ю его в самом начале поставит 1-й)

[avva.livejournal.com]

Они не стремятся к тому, чтобы обойти всю доску. Они стремятся к тому, чтобы выиграть, и для этого им вовсе необязательно, возможно, играть так, чтобы обойти всю доску.

[avva.livejournal.com]

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

[andrew-voland.livejournal.com]

Сорри, выше был я.

[kvasimodo.livejournal.com]

Гм. А стартовое положение коня не имеет значения?
Первый ставит его куда угодно?

[avva.livejournal.com]

Не "куда угодно", а "куда хочет". Он стремится выиграть, как и второй.

[andrew-voland.livejournal.com]

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

Видимо, это преположение неверно. Беим искать другие решения.

[avva.livejournal.com]

Может, верно, может, неверно, но как минимум не доказано ;) если вы хотите его использовать, придётся вначале доказать.

[rowaasr13.livejournal.com]

По-идее (задача о возможности обхода всей доски конём), проиграть должен первый, т.к. 64-й ход будет за вторым. Но так как первый может обломать это решение, выбрав клетку для начала обхода, то выиграет всё-таки он. Так?

[avva.livejournal.com]

Нет ;) не из чего не следует, что они будут играть все 64 хода.

[rowaasr13.livejournal.com]

Ну я про то и говорю. Первый обламывает своим начальным выбором это решение и выигрывает.

[avva.livejournal.com]

Нет, неправильно ;) всё равно ни из чего не следует, что если бы он "обламывал", их оптимальным решением было бы идти все 64 поля.
Не говоря уж о том, что полный обход доски существует начиная с любого поля.

На вскидку

[justsoul.livejournal.com]

1ый выиграет. Ставя коня в угол и "прижимая" его каждым своим ходом к краю.

[avva.livejournal.com]

В принципе, это представляется разумной стратегией. Но задачу нужно решить, дав строгое доказательство.

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

[bengoro.livejournal.com]

первый. количество клеток четное, на последнюю "свободную" встанет второй, а потому первый проигрывает.

[avva.livejournal.com]

Нет, это неверная логика ;) см. комментарии выше.

[botev.livejournal.com]

я там не совсем правильно, видимо, сформулировал. в явном виде стратегию привести можете? она несложная и довольно красивая, я, собственно, только из-за неё задачку и постил.

Re: На вскидку

[dimrub.livejournal.com]

Может, это было бы неплохой стратегией... если бы было возможно. Второй за 3 хода выходит в центр доски.

[avva.livejournal.com]

Ну извините. Я доказал неконструктивно, но доказал ;)

Насчёт стратегии подумаю сейчас.

Re: На вскидку

[justsoul.livejournal.com]

Это вы погорячились.

[justsoul.livejournal.com]

Все оказалось сложнее. Такая стратегия не работает. Пока вариантов больше нет=)

[(Anonymous)]

На самом деле стратегии две. Свой ответ не даю, так как знал ответ на похожую задачу.

[botev.livejournal.com]

я тоже две знаю

Re: На вскидку

[dimrub.livejournal.com]

Да нет, вроде. Если хотите - сыграем :)

[relf.livejournal.com]

Второй всегда выигрывает. Ему достаточно зафиксировать в голове обход конем всей доски, начиная с поля, на которое поставил коня первый игрок, и делать всегда ходы из этого обхода.

[maccolit.livejournal.com]

из общих соображений выигрывает второй
потому что перед ним нечетное число клеток
следовательно последняя незанятая клетка - его

[avva.livejournal.com]

Да, я был неправ. Нашёл стратегию.

[vdots.livejournal.com]

Выигрывает второй. Пусть он мысленно разобьёт доску на 32 непересекающиеся пары клеток так, чтобы в каждой паре клетки были связаны ходом коня (это, очевидно, возможно). На первом ходе он должен пойти на клетку, находящуюся в паре к той, на которой конь стоит изначально. Следующим ходом первый перемещает коня на клетку, парная к которой свободна (потому что единственная использовавшаяся пара израсходована полностью), и потому второй может сделать ход на соответствующую клетку. Продолжая в том же духе, второй сможет сделать ход после каждого хода первого, что и требовалось.

[avva.livejournal.com]

Ага, верно.

[aburachil.livejournal.com]

Пусть x(0),x(1),...,x(64)=x(0) циклический обход доски конём (где-то я читала в детстве, что такой существует ;-) Тогда второй игрок выигрывает, всегда ходя с x(i) на x(i+1), так как ясно, что x(i+1) ещё не использовалась — вторым потому, что он так ходит, а первым потому, что он вообще ходит по клеткам другого цвета. Ну как, правильное решение, или опять лажа как в той задаче, где я не того коня поставила на место короля?

[dimrub.livejournal.com]

Но кто сказал, что первый тоже будет делать ходы из этого обхода?

[relf.livejournal.com]

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

[avva.livejournal.com]

Нет, это правильно.

[dimrub.livejournal.com]

Кто сказал, что на любой ход первого найдется полный обход?

[relf.livejournal.com]

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