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

Условие:

В парламенте у каждого не более трёх врагов. Докажите, что парламент можно разделить на две палаты так, что у каждого парламентария в своей палате будет не более одного врага.

Решение:

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