Построим граф с вершинами r₁, ..., r₅₀, соответствующими строкам доски, и вершинами c₁, ..., c₅₀, соответствующим её столбцам. Вершины r_i и c_j соединим ребром, если клетка в пересечении соответствующих строки и столбца свободна. Тогда Васина цель переформулируется так: требуется отметить не более 99 рёбер так, чтобы из каждой вершины выходило чётное число непомеченных рёбер. Действительно, если Вася поставит фишки в клетки, соответствующие отмеченным рёбрам, то в каждой строке и каждом столбце останется чётное число свободных клеток.

  Мы докажем более общий факт: в любом графе на  n ≥ 2  вершинах можно отметить не более  n – 1  ребра так, чтобы из каждой вершины выходило чётное число непомеченных рёбер.

  Индукция по n. База  (n = 2)  очевидна.

  Шаг индукции. Пусть  n > 2.  Если в графе есть вершина степени 0, то достаточно выкинуть её и применить предположение индукции.

  Если есть вершина степени 1, то можно пометить единственное ребро, выходящее из неё, выкинуть её вместе с этим ребром и применить к оставшемуся графу предположение индукции.

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

Ответ задачи отсутствует