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