23:37 

Игра

wpoms.
Step by step ...


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



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

Комментарии
2018-01-03 в 15:23 

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

2018-01-03 в 19:08 

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

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

URL
2018-01-03 в 19:28 

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

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

2018-01-03 в 20:42 

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

2018-01-03 в 20:52 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Alemand, Но не работает и центральная симметрия центральный квадрат (51; 51). и на ход (51;52) ответ (51;50) не проходит.(три в ряду).
хм... согласен... :upset:

2018-01-04 в 13:54 

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

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

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

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

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

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

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

URL
2018-01-05 в 00:37 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Гость, извините... но я мало что понял в Вашем решении... :nope: :pom:

2018-01-05 в 00:42 

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

URL
2018-01-05 в 11:52 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Гость, аааа... понятно... :alles:
Кстати, с перестановкой строк и столбцов - интересная идея...

2018-01-05 в 17:47 

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

URL
2018-01-19 в 22:41 

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

2018-01-20 в 00:10 

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

2018-01-20 в 20:34 

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

2018-01-28 в 18:57 

Нет, кривое решение привел. По сути тут 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 линии), а оттуда уже вывод делать о том, кто одержит победу. Правда муторно вроде как.

2018-01-28 в 21:34 

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

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

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

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

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

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

или

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

или

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

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

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

или

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

или

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

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

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

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

Для 3х3

хо-
х-о
-х-

или

хо-
х-о
--х

или

хо-
-хо
х--

или

хо-
-хо
--х

или

хо-
о-х
-х-

или

хо-
о-х
--х

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

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

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

и так далее

URL
     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная