Решение задачи 360

Условие:

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

Решение:

Рассмотрим величину: количество дорог, соединяющих города с различными цветами флагов. Заметим, что каждое утро это величина уменьшается. Действительно, пусть в городе А висит белый и флаг и пусть у города А соседей с черным флагом больше половины, n соседей с черным флагом и m -- с белым (n>m). Тогда в городе А флаг поменяется на черный и рассматриваемая величина уменьшится на n и увеличится на m, то есть в итоге уменьшится. Осталось заметить, что количество дорого является целым неотрицательным числом, поэтому уменьшаться вечно не может, значит процесс закончится.

Ответ: Не может.