Игра

[wpoms.]

Августин и Лукас по очереди помечают квадраты на доске размером `101xx101` квадратов. Августин начинает игру. Нельзя помечать квадрат, если в том же ряду или столбце уже помечены два квадрата. Тот, кто не может пометить квадрат, проигрывает. Кто имеет выигрышную стратегию?

@темы: Дискретная математика

Comments

[Alemand]

Думаю, что выигрышная стратегия имеется у первого из игроков. Первый ход: помечаем квадрат (101; 101).
По аналогии с матрицей назовем главной диагональю диагональю диагональ где номер столбца совпадает с номером строки.
Если ход второго игрока приходится на главную диагональю то ответ первого симметричен относительно центрального квадрата. ( к примеру (1;1) - (201; 201)
В других случаях ответный ход первого игрока симметричен относительно главной диагонали ( к примеру (9;4) - (4; 9)

[Гость]

Рассмотрим доску 3 на 3.

Последовательность ходов - (2,2) - (2,1) - (1,2) - (3,1) - (1,3) - (3,3) - приводит к победе второго игрока.

[All_ex]

Alemand, к примеру (1;1) - (201; 201)
Дык, доска всего `101 xx 101`... хотя мысль понятна...

Я думаю, что выигрыш у первого игрока, если он сходит первым ходом в `(50;50)`, а потом отвечает симметрично этой центральной клетке... то есть на ход `(i;j)` отвечает `(102-i;102-j)`...

[Alemand]

Действительно, не работает. Но не работает и центральная симметрия центральный квадрат (51; 51). и на ход (51;52) ответ (51;50) не проходит.(три в ряду).

[All_ex]

Alemand, Но не работает и центральная симметрия центральный квадрат (51; 51). и на ход (51;52) ответ (51;50) не проходит.(три в ряду).
хм... согласен...

[Гость]

_|x|x
- - -
0|x|_
- - -
0|_|0

Если поменять местами 3 и 2 столбцы,

_|x|x
- - -
0|_|x
- - -
0|0|_

то новых возможностей не появится.

Аналогично, если поменять местами 1 и 2 строки исходной конфигурации

0|x|_
- - -
_|x|x
- - -
0|_|0

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

[All_ex]

Гость, извините... но я мало что понял в Вашем решении...

[Гость]

Здесь нет решения, лишь совет не искать симметрию и прочую красоту.

[All_ex]

Гость, аааа... понятно...
Кстати, с перестановкой строк и столбцов - интересная идея...

[Гость]

Возможно, если проанализировать развитие ситуации вблизи одного угла таблицы, то можно будет сделать предположение о стратегии второго игрока.

[Груша Вильямс]

Выигрышную стратегию, думаю, имеет второй. Куда бы не поставил первый "крестик" мы в ответ ставим под (над) ним "нолик", тем самым отбрасываем этот столбец и фактически получаем доску 101 x 100 и т.д. Какого бы размера доска ни была, второй всегда может поставить "нолик" в столбик после одной занятой клетки "крестика" первого. Таким образом задача сводится фактически к полосе 2 x 101.

[All_ex]

Груша Вильямс, в условии не только про столбики, но и про строчки говорится...
Например, для таблицы `3 xx 3` Ваш план даёт такую игру
`((x1, x2, - ), (01, 02, - ), ( - , - , x3))`
и второму ходить некуда...

[Груша Вильямс]

All_ex, а да, что-то забыл)) А такой вариант, используя стратегию доводим до квадрата 3x3 и там её меняем. Я конечно понимаю что мы можем и не дойти до квадрата 3x3 если первый будет ходить "не последовательно", но, вроде бы, мы можем начинать его склеивать когда используем уже 98 столбцов, т.е. задача сведётся опять к квадрату 3x3.

[Груша Вильямс]

Нет, кривое решение привел. По сути тут 3 варианта есть - не вычеркнуть линию, вычеркнуть одну или две.
А. Первым ходом игрок не может вычеркнуть линию - 0, а второй может - 1. Вторым ходом первый уже может вычеркнуть линию - 1, а второй может вычеркнуть уже две - 2 либо 1 либо 0. Обозначим эту стратегию как 01,12 либо 01,11, либо 01,10. Назовём эти стратегии A1, A2 и A3 соответственно. Стратегия А1 - будет повторяться, если так дальше и продолжать. Стратегии А2 и А3 не рассматривал.
Б. Первым ходом игрок не может вычеркнуть линию - 0, а второй может вычеркнуть - 1. Вторым ходом первый уже может не вычеркнуть линию - 0, а второй может вычеркнуть уже две - 2 (может ещё и одну, и не вычеркнуть, их не рассматривал). Тогда первый может вычеркнуть одну линию либо не вычеркнуть - 1 либо 0 (больше нет вариантов), тогда если второй вычеркнет две (при условии что первый вычеркнул 1), то первый ничего уже не вычеркнет - 0 (т.е. цикл закончится), если второй вычеркнет одну (при условии что первый вычеркнул 1), то первый сможет вычеркнуть либо 0 (цикл закончится), либо 1. Стратегии 01,02,12,0 либо 01,02,11,0 либо 01,02,11,1.
Вобщем идея рассмотреть все стратегии, а потом по разному пробовать суммировать, чтоб сумма 202 получилась (202 линии), а оттуда уже вывод делать о том, кто одержит победу. Правда муторно вроде как.

[Гость]

Пусть первый сделал первый ход в (1,1)

х------
-------
-------

Тогда второй пойдет в (1,2)

хо-----
-------
-------

У первого есть три возможности для ответного хода:

хо-----
х-----
-------

или

хо-----
-х-----
-------

или

хо-----
--х----
-------

Ответные ходы второго:

хо-----
х-о---
-------

или

хо-----
-хо----
-------

или

хо-----
о-х----
-------

Это приводит к уменьшению игрового поля до 99х100

В дальнейшем второй игрок сможет уменьшать размеры игрового поля на 1 при каждом своем ходе.

В конце игры останется поле 1х2 перед ходом первого игрока.

Для 3х3

хо-
х-о
-х-

или

хо-
х-о
--х

или

хо-
-хо
х--

или

хо-
-хо
--х

или

хо-
о-х
-х-

или

хо-
о-х
--х

И второй выигрывает

Продолжения, уменьшающие на 1 размер доски

хо-------
х-о------
-х-о-----
---------
---------

и так далее