|
|
 |
Условие
Петя поставил на доску 50×50 несколько фишек, в каждую клетку – не больше одной. Докажите, что у Васи есть способ поставить на свободные поля этой же доски не более 99 новых фишек (возможно, ни одной) так, чтобы по-прежнему в каждой клетке стояло не больше одной фишки, и в каждой строке и каждом столбце этой доски оказалось чётное количество фишек.
Решение
Построим граф с вершинами r1, ..., r50, соответствующими строкам доски, и вершинами c1, ..., c50, соответствующим её столбцам. Вершины ri и cj соединим ребром, если клетка в пересечении соответствующих строки и столбца свободна. Тогда Васина цель переформулируется так: требуется отметить не более 99 рёбер так, чтобы из каждой вершины выходило чётное число непомеченных рёбер. Действительно, если Вася поставит фишки в клетки, соответствующие отмеченным рёбрам, то в каждой строке и каждом столбце останется чётное число свободных клеток.
Мы докажем более общий факт: в любом графе на n ≥ 2 вершинах можно отметить не более n – 1 ребра так, чтобы из каждой вершины выходило чётное число непомеченных рёбер.
Индукция по n. База (n = 2) очевидна.
Шаг индукции. Пусть n > 2. Если в графе есть вершина степени 0, то достаточно выкинуть её и применить предположение индукции.
Если есть вершина степени 1, то можно пометить единственное ребро, выходящее из неё, выкинуть её вместе с этим ребром и применить к оставшемуся графу предположение индукции.
Пусть теперь степень каждой вершины не меньше 2. Выйдем из произвольной вершины по ребру, из вершины, в которую мы пришли – по другому ребру, и т.д.; этот процесс можно продолжать, пока мы не вернёмся в вершину, в которой уже побывали. Таким образом, в графе нашёлся цикл. Выкинув его рёбра из графа, мы не изменим чётностей степеней вершин; значит, достаточно отметить требуемые рёбра в оставшемся графе. Применяя к нему тот же процесс, рано или поздно мы получим граф, в котором степень некоторой вершины не превосходит 1; а для таких графов утверждение уже доказано.
