Задание №176717: Турнир городов

2) В каждом столбце есть хотя бы один плюс. Пусть начинает Миша. Паша мысленно отмечает
по одному плюсу в каждом столбце. Пока есть строки без отмеченных плюсов, Паша вычёркива-
ет их. Когда они закончатся, количество оставшихся отмеченных плюсов будет равно количеству
оставшихся строк (Миша каждым ходом вычеркивал ровно один отмеченный плюс), то есть в

каждой строке и каждом столбце останется по одному отмеченному плюсу. Далее Паша каждый
раз вычеркивает строку, содержащую отмеченный плюс, только что вычеркнутый Мишей. В ре-
зультате в конце останется клетка с отмеченным плюсом, то есть выиграет Паша.
Решение 4. Пусть начинает Паша. Покажем, что у него есть выигрышная стратегия в том и
только том случае, если имеется строка из одних плюсов.
Если такая строка есть, то пусть Паша её не вычёркивает. Тогда в конце остаётся клетка этой
строки, а в ней стоит плюс и Паша выигрывает.

Наоборот, пусть в каждой строке есть минус. Докажем, что Миша может действовать так, что-
бы всё время сохранять это свойство (тогда в конце останется клетка с минусом и Миша выиграет).
Предположим противное и рассмотрим первый шаг, когда Миша не может сделать нужный ход, а
именно: какой бы столбец он не вычеркнул, появится строка из одних плюсов. Тогда для каждого
столбца есть строка, содержащая ровно один минус, причём именно в этом столбце. Эти строки
различны для всех столбцов, поэтому всего строк не меньше, чем столбцов. Но после хода Паши
всего строк на 1 меньше, чем столбцов — противоречие.
Аналогично доказывается, что если начинает Миша, то у него есть выигрышная стратегия в
том и только том случае, когда имеется столбец из одних минусов. Но если есть такой столбец, то

не может быть строки из одних плюсов. Поэтому если есть выигрышная стратегия у начинающего
Миши, то не может быть выигрышной стратегии у начинающего Паши, что и требовалось.