Задача 78818
|
|
 |
Условие
В городе "Многообразие" живут n жителей, любые два из которых либо дружат, либо враждуют между собой. Каждый день не более чем один житель может начать новую жизнь: перессориться со всеми своими друзьями и подружиться со всеми своими врагами. Доказать, что все жители могут подружиться.Примечание. Если A — друг B, а B — друг C, то A — также друг C. Предполагается также, что среди любых троих жителей хотя бы двое дружат между собой.
Решение
Пусть A, B и C — какие-то три жителя города.Ясно, что возможен случай, когда все они дружат между собой; возможно также, что один из них (скажем, A) не дружит ни с B, ни с C, а B и C дружат между собой: тогда для того, чтобы A, B и C все подружились, достаточно, чтобы A "начал новую жизнь".
Нетрудно также видеть, что два других случая: когда все три жителя A, B и C между собой враждуют и когда один житель, — например, тот же A, — дружит с B и с C, а те враждуют между собой, уже невозможны.
Описанное строение "отношения дружбы" между любыми тремя лицами A, B и C доказывает, что в пределах всего города это отношение можно описать весьма просто: в городе имеются две группы жителей (две партии M и N, такие, что все жители принадлежат либо к одной, либо к другой партии (но никогда — к обеим сразу), причём каждые два члена одной партии между собой дружат, а жители, принадлежащие к разным партиям, обязательно враждуют. В самом деле, присоединим к нашим трем жителям A, B и C города Многообразие еще одного жителя D; в таком случае, если A и B дружат между собой и D дружит хоть с одним из них, то он дружит и со вторым — и, значит, принадлежит к партии, в которую входят и A, и B; если же A и B между собой враждуют, то D дружит лишь с одним из них (но с одним дружит непременно!). Это рассуждение обеспечивает возможность разбиения четвёрки жителей A, B, C и D на две партии M и N (впрочем, одна из этих партий может быть и "пустой": так будет, если все жители A, B, C и D дружат между собой). Поступая так же и дальше, т. е. последовательно присоединяя к уже рассмотренным жителям города по одному человеку, мы докажем возможность разбиения на две партии всех n жителей города.
Теперь доказательство утверждения задачи не представляет уже никакого труда. Если все жители города дружат между собой, то нам и доказывать нечего; если же ни одна из партий M и N не "пуста", то мы предложим каждый день одному из участников партии M "начинать новую жизнь", т. е., попросту, переходить в партию N. Если в партии M имеется k человек, то все жители города смогут подружиться за k дней.
