Олимпиадные задачки про доску с клетками.

[never-sleep]

1) Петя и Вася играют в игру: они по очереди (начинает Петя) ставят фишки в клетки доски $2012x2012$. Выигрывает тот, после хода которого в каждом квадрате $2x2$ будет стоять хотя бы одна фишка. Кто из игроков имеет выигрышную стратегию?

Если рассматривать простую стратегию "в лоб", то можно просто разбить доску на сегменты $2x2$ и ставить по одной фишке в каждый сегмент по очереди. Тогда выйдет, что сегментов будет $503 x 503$. То есть нечетное количество и выигрывает Петя. Но ведь помимо этого есть масса других стратегий. Ведь Вася должен догадаться, что не нужно использовать простую стратегию. Но какую же стратегию ему использовать. Нужно портить сегменты Пети. Но ведь можно по одной фишке подсовывать в сегменты, по 2, по 3. В каждый сегмент подсовывать или нет -- тоже еще вопрос. То есть вариантов очень много. Можете, пожалуйста, подсказать -- в какую сторону думать?

2) Петя и Вася играют в игру на доске $4x25$. Они по очереди (начинает Петя) ставят ладей на свободные клетки доски. При этом Петя может ставить ладей под бой четного числа уже поставленных ладей, а Вася -- под бой нечетного числа уже поставленных ладей (ладьи не бьют сквозь друг друга). Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Можете подсказать с чего начать? Ладьи подразумеваются одноцветные?

[Someone]

never-sleep в сообщении #900969 писал(а):

можно просто разбить доску на сегменты $2x2$ и ставить по одной фишке в каждый сегмент по очереди. Тогда выйдет, что сегментов будет $503 x 503$

Почему это вдруг $503\times 503$? А в квадрате $4\times 4$ сколько будет сегментов? Неужели всего один?

never-sleep в сообщении #900969 писал(а):

Нужно портить сегменты Пети.

В каком смысле "портить"? Добавление лишних фишек в сегмент его не портит, в нём "хотя бы одна" фишка имеется.

never-sleep в сообщении #900969 писал(а):

Ладьи подразумеваются одноцветные?

Да.

P.S. Знак умножения в виде косого креста — \times. А вообще, в теме "Краткий ФАК по тегу [math]." много всяких значков можно найти.

[never-sleep]

Спасибо! Ох, точно $1006\times 1006$, тогда выигрывает Вася!
Портит -- значит сбивается расставление по 1 фишке в сегмент, далее считать сложнее. Как лучше это учесть?

[Someone]

never-sleep в сообщении #901055 писал(а):

Ох, точно $1006\times 1006$

Ой ли! Я вот в квадрате $4\times 4$ насчитал $9$ штук.

[Cash]

1) Разберитесь, кто выигрывает на доске $2\times n$

[never-sleep]

Someone в сообщении #901067 писал(а):

Ой ли! Я вот в квадрате $4\times 4$ насчитал $9$ штук.

Точно, вы правы, гораздо больше.

-- 28.08.2014, 11:19 --

Cash в сообщении #901119 писал(а):

1) Разберитесь, кто выигрывает на доске $2\times n$

ОК, пока что рассматриваю при $n=8$
Понимаю, что сегментов будет не 4, а гораздо больше. Для начала рассмотрю последовательно идущие 4 квадрата $2\tines 2$. Далее пишу именно про эти 4 сегмента.
Если будут играть в простую игру, выставляя по одной фишке в каждый сегмент, то выиграет Вася.
Если по 2 фишки в каждый сегмент будут ставить, то выиграет снова Вася.
Если по 3 фишки в каждый сегмент будут ставить, то выиграет снова Вася.
Если по 4 фишки в каждый сегмент, то выиграет Петя.
Ясно, что здесь есть много промежуточных вариантов еще. Пока что верно или нет?

[Cash]

Неверно.
Они играют в одну игру, а не в четыре.
Начните со случая $2\times 4$. Сколько здесь всего квадратов?
И просто переберите все варианты игры (сыграйте сами с собой, пытаясь выиграть за каждую сторону).
Перейдите потом к $2\times 5$, далее $2\times 6$
может и найдете закономерность.

[never-sleep]

Cash в сообщении #901189 писал(а):

Неверно.
Они играют в одну игру, а не в четыре.
Начните со случая $2\times 4$. Сколько здесь всего квадратов?
И просто переберите все варианты игры (сыграйте сами с собой, пытаясь выиграть за каждую сторону).
Перейдите потом к $2\times 5$, далее $2\times 6$
может и найдете закономерность.

В случае $2\times 4$ будет 3 квадрата и выигрышная стратегия у Пети (выиграет за 2 хода).
В случае $2\times 5$ будет 4 квадрата и выигрышная стратегия у Пети (выиграет за 3 хода).
В случае $2\times 6$ будет 5 квадрата и выигрышная стратегия у Пети (выиграет за 4 хода).
В случае $2\times n$ будет $n-1$ квадратов и выигрышная стратегия у Пети (выиграет за $n-2$ хода).
Верно ли это?

[Johnston]

В порядке бреда. Возможно, следует обдумать симметричные ходы и занятие центральной ячейки.

[TOTAL]

never-sleep в сообщении #901308 писал(а):

В случае $2\times 4$ будет 3 квадрата и выигрышная стратегия у Пети (выиграет за 2 хода).
Верно ли это?

Петя начинает, затем ходит Вася, а Пете ходить некуда.

[never-sleep]

У Пети нечетные номера. Потому, чтобы попасть каждый квадрат, примерно вот так должна развиваться игра. Тут Петя выигрывает все время (потому как в конце нечетный номер). Правильно?

[Someone]

never-sleep в сообщении #901587 писал(а):

Правильно?

Неправильно. На поле $2\times 4$ выигрывает Вася. За два хода: Петя ставит фишку куда-нибудь, затем делает ход Вася и выигрывает. Вам об этом уже написали.

[TOTAL]

never-sleep в сообщении #901587 писал(а):

У Пети нечетные номера. Потому, чтобы попасть каждый квадрат, примерно вот так должна развиваться игра. Тут Петя выигрывает все время (потому как в конце нечетный номер). Правильно?

В углах всех клеток (но не на границе области) поставим по колышку. Ходом на какую-то клетку игрок сбивает все колышки, стояшие в углах этой клетки. Выигрывает тот, кто собьет последние колышки. На доске $4 \times 2$ всего $3$ колышка.

На доске $n \times 2$ при $n>3$ второй игрок дожидается момента, когда на доске останутся один или два рядом стоящих колышка и уничтожает их, т.е. выигрывает.

[never-sleep]

Someone в сообщении #901592 писал(а):

never-sleep в сообщении #901587 писал(а):

Правильно?

Неправильно. На поле $2\times 4$ выигрывает Вася. За два хода: Петя ставит фишку куда-нибудь, затем делает ход Вася и выигрывает. Вам об этом уже написали.

Точно, понятно, извиняюсь, что туплю.

-- 30.08.2014, 12:47 --

TOTAL в сообщении #901598 писал(а):

never-sleep в сообщении #901587 писал(а):

У Пети нечетные номера. Потому, чтобы попасть каждый квадрат, примерно вот так должна развиваться игра. Тут Петя выигрывает все время (потому как в конце нечетный номер). Правильно?

В углах всех клеток (но не на границе области) поставим по колышку. Ходом на какую-то клетку игрок сбивает все колышки, стояшие в углах этой клетки. Выигрывает тот, кто собьет последние колышки. На доске $4 \times 2$ всего $3$ колышка.

А почему 3 колышка, а не 4?


-- 30.08.2014, 12:51 --

TOTAL в сообщении #901598 писал(а):

На доске $n \times 2$ при $n>3$ второй игрок дожидается момента, когда на доске останутся один или два рядом стоящих колышка и уничтожает их, т.е. выигрывает.

Хорошо, спасибо. А как обобщать? После $2\times n$ лучше брать $3\times n$ ?

-- 30.08.2014, 12:57 --

Я ведь неправильно понял про колышки, да?
Точки -- колышки. Крестики-- ходы.

[TOTAL]

never-sleep в сообщении #902046 писал(а):

Я ведь неправильно понял про колышки, да?
Точки -- колышки. Крестики-- ходы.

Колышки стоят на пересечении линий сетки.