Problem 1552

11.8. См. решение задачи 10.8.

Построим граф с вершинами $r_1, \dots, r_{50}$, соответствующими строкам доски, и вершинами $c_1, \dots, c_{50}$, соответствующим её столбцам. Вершины $r_i$ и $c_j$ соединим ребром, если клетка в пересечении соответствующих строки и столбца свободна. Тогда Васина цель переформулируется так: требуется отметить не более $99$ ребер так, чтобы из каждой вершины выходило чётное число непомеченных рёбер. Действительно, если Вася поставит фишки в клетки, соответствующие отмеченным рёбрам, то в каждой строке и каждом столбце останется чётное число свободных клеток, что, очевидно, равносильно требуемому условию.

Мы докажем более общий факт: в любом графе на $n \ge 2$ вершинах можно отметить не более $n-1$ ребра так, чтобы из каждой вершины выходило чётное число непомеченных рёбер. При $n = 100$ получаем требуемое утверждение.

Индукция по $n$. База при $n=2$ очевидна. Пусть теперь $n > 2$. Если есть вершина степени $1$, то можно пометить единственное ребро, выходящее из неё, выкинуть её вместе с этим ребром и применить к оставшемуся графу предположение индукции; в результате окажется отмеченным ещё $n-2$ ребра. Если в графе есть вершина степени $0$, то достаточно выкинуть её и применить предположение индукции.

Пусть теперь степень каждой вершины не меньше $2$. Выйдем из произвольной вершины по ребру, из вершины, в которую мы пришли — по другому ребру, и т.д.; этот процесс можно продолжать, пока мы не вернёмся в вершину, в которой уже побывали. Таким образом, в графе нашёлся цикл. Выкинув его рёбра из графа, мы не изменим чётностей степеней вершин; значит, достаточно отметить требуемые рёбра в оставшемся графе. Применяя к нему тот же процесс, рано или поздно мы получим граф, в котором степень некоторой вершины не превосходит $1$; а для таких графов утверждение уже доказано выше.