2019-04-29
В городе «Многообразие» живут 10 000 жителей, каждые два из которых либо враждуют, либо дружат между собой. Каждый день не более чем один житель города может «начать новую жизнь», т.е. перессориться со всеми своими друзьями и подружиться со всеми врагами; при этом любые три жителя могут подружиться между собой. Доказать, что все без исключения жители могут подружиться между собой. Какого наименьшего числа дней наверное достаточно для этого?
Решение:
Пусть $A, B$ и $C$ - какие-то три жителя города. Ясно, что возможен случай, когда все они дружат между собой, возможно также, что один из них (скажем, $A$) не дружит ни с $B$, ни с $C$, а $B$ и $C$ дружат между собой: тогда для того, чтобы $A, B$ и $C$ все подружились, достаточно, чтобы $A$«начал новую жизнь». Нетрудно также видеть, что два других случая: когда все три жителя $A, B$ и $C$ между собой враждуют и когда один житель,- например, тот же $A$,- дружит с $B$ и с $C$, а те враждуют между собой, уже невозможны: в этих случаях среди трех пар $A, B$; $A, C$ и $B, C$ жителей Многообразия имеется нечетное (3 или 1) число в пар врагов и четное (0 или 2) число $d$ пар друзей; при любых изменениях отношений в этой тройке лиц (во всех случаях, когда $A, B$ или $C$ «начинают новую жизнь») четность чисел $b$ и $d$ не меняется (нечетное число в может замениться лишь нечетным же числом $b'$, а четное число $d$ - четным же числом ($d'$), в силу чего все лица $A, B$ и $C$ никогда не смогут подружиться между собой (число $b$ не сможет стать равным 0).
Описанное строение «отношения дружбы» между любыми тремя лицами $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$ дружат между собой). Поступая так же и дальше, т.е. последовательно присоединяя к уже рассмотренным жителям города по одному человеку, мы докажем возможность разбиения на две партии всех 10000 жителей города.
Теперь доказательство утверждения задачи не представляет уже никакого труда. Если все жители города дружат между собой, то нам и доказывать нечего; если же ни одна из партий $M$ и $N$ не «пуста», то мы предложим каждый день одному из участников партии $M$ «начинать новую жизнь», т. е. попросту, переходить в партию $N$. Если в партии $М$ имеется $k$ человек, то все жители города смогут подружиться за $k$ дней; отсюда ясно, что 5000 дней ($\approx 14$ лет) заведомо будет достаточно для того, чтобы все жители города смогли подружиться (ибо хоть одна из партий $M$ и $N$ содержит не более 5000 членов).
Ответ: 5000 дней (в городе существуют две такие партии, что два жителя дружат в том и только в том случае, когда они принадлежат к одной партии).