Пусть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дней.

Ответ задачи отсутствует