игровая задача

Имеется квадратное поле (наподобие шахматной доски) размером п*п.

Камень лежит в левом нижнем углу.
Игроки ходят по очереди.
Каждый игрок должен переложить камень в одну из соседних клеток, но перекладыватать на те клетки где камень уже лежал запрещено.
Тот игрок, которому некуда ходить, считается проигравшим.

Доказать что когда п четно то один из игроков всегда выигрывает при правильной игре
а когда п нечетно другой выигрывает при правильной игре

тут тебе вряд ли помогут, сходи на алголист

пока вижу два варианта
1) найти некий инвариант, например что у 1-го при четном n будет всегда куда походить.
значит, тк поле ограничено, то второй не сможет сделать ход когда-нить
2) пойти с конца. рассмотреть ситуацию, когда один проиграл. потом отмотать на шаг назад, и посмотреть, что ей преджествовало. потом еще на шаг. и так дойти до первой клетки.
Доказав, что так будет все время.

3) (фиг его) найти/построить оптимальные стратегии для игроков(включает первые два:) )

Смотри если п четно

то замомстим доску фишками от домино, так чтобы фишки не пересекались и покравали всю доску.

тогда первый игрок должен всегда ходить так чтобы покрывать вторую часть фишки домино

Очевиднее будет так:

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

Цитата Visitor,4.01.04, 14:38

Очевиднее будет так:

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

очевидней но неправильней


игроки всегда ходят на свой цвет иначе никак не получмтся но не всегда они могут гарантировать себе выигрыш

Цитата Guest,4.01.04, 14:49

Цитата Visitor,4.01.04, 14:38

Очевиднее будет так:

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

очевидней но неправильней


игроки всегда ходят на свой цвет иначе никак не получмтся но не всегда они могут гарантировать себе выигрыш

эсперанто это сказал

Почему не могут? Форсированному проигрышу одного из игроков предшествовала бы ситуация, когда после его хода свободные (те, на которых камень еще не был) клетки доски разделились на две несвязные области, в одной из которых нечетное количество клеток. Следовательно, таких ходов игрок делать не может. А если такие области содержат четное количество клеток -- можно просто посчитать клетки разного цвета

на доске 3*3 второй всегда выигрывает

если же лн будет следовать вашему правилу то он иожет проиграть

например

(1,2) белое поле ход первого
(2,2) черное поле ход второго
(2,3) белое поле 1-й
(3,3) черное второй
(3,2) белое 1-й
(3,1) чероное 2-й
(2,1) белое первый.

и все второй проиграл, хотя мог однозначно выиграть пользуясь стратегией домино

Угу, я сразу не въехал -- праздники понимаешь Теперь вижу.

После
3. (2,3) 1й белое
второй форсированно выигрывает по приведенному выше правилу

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

BTW, на доске 3х3 (и не только) всегда выигрывает первый, сделав ход в клетку того цвета, которых больше... И всегда проигрывает, не сделав етот ход.

Сообщение отредактировано: Visitor - 05.01.04, 07:46