|
|
 |
Условие
У Паши и Миши есть квадратная таблица $100\times100$, в каждой клетке которой стоит либо плюс, либо минус. Паша и Миша по очереди вычёркивают: Паша — ещё не вычеркнутую строку, а Миша — ещё не вычеркнутый столбец, пока не останется всего одна невычеркнутая клетка. Если в ней стоит плюс, то выиграл Паша, а если минус — Миша. Могла ли таблица оказаться такой, что в этой игре, кто бы её ни начинал — Паша или Миша, — способ гарантировать себе победу имеетсяа) у того, кто ходит вторым;
б) у начинающего?
Решение
а) Рассмотрим таблицу, где плюсы и минусы расставлены в шахматном порядке. Пусть игрок, который ходит вторым, каждым ходом вычеркивает ряд, пересекающий главную диагональ, состоящую из «его» знаков, в клетке, которую перед этим вычеркнул его противник. Тогда последняя невычеркнутая клетка лежит на этой диагонали, то есть приносит победу второму.
б) Решение 1. Предположим, что у Паши есть выигрышная стратегия, когда он начинает. Тогда в игре, где Паша ходит вторым, пусть он игнорирует первый ход Миши (будто его не было) и применяет свою выигрышную стратегию. Сделав свой последний ход, Паша может считать, что это он начинал, и только сейчас Миша сделал тот самый ход, который на самом деле у Миши был первым. Значит, тут снова выиграет Паша, а не начинавший Миша.
Вариация решения 1. Предположим, что у Паши есть выигрышная стратегия, когда он начинает. Тогда в игре, где Паша ходит вторым, пусть он действует по своей выигрышной стратегии, делая свой первый ход по этой стратегии, а второй ход — тот, который надо сделать в ответ на первый ход Миши, и так далее (то есть каждый раз он как бы запаздывает с ответом, отвечая на более ранний ход Миши). Тогда Паша выиграет, ответив своим последним ходом на предпоследний ход Миши (поскольку последний ход Миши уже не имеет значения — не важно, сделан ли он до хода Паши или после).
Решение 2. Назовём таблицу, для которой способ гарантировать себе победу имеется у начинающего, кто бы это ни был, хорошей.
Докажем следующую лемму.
Лемма. Если существует хорошая таблица $S$ размерами $(n+1)\times(n+1)$, то существует и хорошая таблица $T$ размерами $n\times n$.
Пусть для таблицы $S$ начинающий Паша побеждает, вычёркивая первым ходом строку $a$, а начинающий Миша побеждает, вычёркивая первым ходом столбец $b$. Рассмотрим таблицу $T$ размерами $n\times n$, полученную из $S$ вычёркиванием строки $a$ и столбца $b$. Докажем, что в ней снова выигрывает начинающий.
В самом деле, если начинающий — Паша, то для таблицы $S$ он вычеркнул бы строку $a$, и если бы Миша в ответ вычеркнул столбец $b$, Паша всё равно сумел бы выиграть. Но при этом как раз осталась бы таблица $T$, и Паша как раз начинает. Аналогично разбирается случай, когда начинающий — Миша. Лемма доказана.
Предположим теперь, что существует хорошая таблица размерами $100\times100$. Использовав лемму 99 раз, получим, что существует хорошая таблица размерами $1\times1$. Но в такой таблице стоит лишь один определённый знак, и если это плюс, то всегда выиграет Паша, а если минус — Миша, то есть таблица не является хорошей, противоречие.
Решение 3. Рассмотрим два случая.
1) В таблице есть столбец из одних минусов. Пусть начинает Паша. Тогда Миша выиграет, если не будет вычёркивать этот столбец (Паша за 99 ходов не сможет вычеркнуть из него все минусы).
2) В каждом столбце есть хотя бы один плюс. Пусть начинает Миша. Паша мысленно отмечает по одному плюсу в каждом столбце. Пока есть строки без отмеченных плюсов, Паша вычёркивает их. Когда они закончатся, количество оставшихся отмеченных плюсов будет равно количеству оставшихся строк (Миша каждым ходом вычеркивал ровно один отмеченный плюс), то есть в каждой строке и каждом столбце останется по одному отмеченному плюсу. Далее Паша каждый раз вычеркивает строку, содержащую отмеченный плюс, только что вычеркнутый Мишей. В результате в конце останется клетка с отмеченным плюсом, то есть выиграет Паша.
Решение 4.
Пусть начинает Паша. Покажем, что у него есть выигрышная стратегия в том и только том случае, если имеется строка из одних плюсов.
Если такая строка есть, то пусть Паша её не вычёркивает. Тогда в конце остаётся клетка этой строки, а в ней стоит плюс и Паша выигрывает.
Наоборот, пусть в каждой строке есть минус. Докажем, что Миша может действовать так, чтобы всё время сохранять это свойство (тогда в конце останется клетка с минусом и Миша выиграет). Предположим противное и рассмотрим первый шаг, когда Миша не может сделать нужный ход, а именно: какой бы столбец он не вычеркнул, появится строка из одних плюсов. Тогда для каждого столбца есть строка, содержащая ровно один минус, причём именно в этом столбце. Эти строки различны для всех столбцов, поэтому всего строк не меньше, чем столбцов. Но после хода Паши всего строк на 1 меньше, чем столбцов — противоречие.
Аналогично доказывается, что если начинает Миша, то у него есть выигрышная стратегия в том и только том случае, когда имеется столбец из одних минусов. Но если есть такой столбец, то не может быть строки из одних плюсов. Поэтому если есть выигрышная стратегия у начинающего Миши, то не может быть выигрышной стратегии у начинающего Паши, что и требовалось.
Ответ
а) Могла;б) не могла.
