Разделы 
Дополнительно
Задача по математике - 3791
2019-06-16 
В парламенте у каждого его члена не более трех врагов. Докажите, что парламент можно разбить на две палаты так, что у каждого парламентария в одной с ним палате будет не более одного врага. (Считается, что если $B$ - враг $A$, то $A$ - враг $B$.)
Решение:
Рассадим сначала парламентариев по двум палатам произвольным образом. Если в какой-то палате у ее члена $A$ не менее двух врагов, то в другой палате у $A$ не более одного врага. Пересадим $A$ в другую палату; при этом суммарное количество $s$ пар врагов в той и другой палате уменьшается. Поскольку $s$ - целое неотрицательное число, такое уменьшение $A$ может быть проделано лишь конечное число раз, и в результате получится требуемое разбиение на палаты.
В парламенте у каждого его члена не более трех врагов. Докажите, что парламент можно разбить на две палаты так, что у каждого парламентария в одной с ним палате будет не более одного врага. (Считается, что если $B$ - враг $A$, то $A$ - враг $B$.)
Решение:
Рассадим сначала парламентариев по двум палатам произвольным образом. Если в какой-то палате у ее члена $A$ не менее двух врагов, то в другой палате у $A$ не более одного врага. Пересадим $A$ в другую палату; при этом суммарное количество $s$ пар врагов в той и другой палате уменьшается. Поскольку $s$ - целое неотрицательное число, такое уменьшение $A$ может быть проделано лишь конечное число раз, и в результате получится требуемое разбиение на палаты.
