Всем привет! Начну свой канал следующей интересной задачей, имеющей название "Задача о попарных знакомствах". Суть ее в следующем: среди ЛЮБЫХ 6 людей либо существует 3 человека, что внутри этой троицы каждый знаком с каждым, либо существует 3 человека, что внутри этой троицы никто никого не знает. Давайте попробуем это доказать. Итак, у нас есть 6 человек и пусть они знакомы некоторым образом(если 2 человека знакомы, соединим их имена линией):
Но нас интересует общий случай, а не один конкретный пример. Для общего случая давайте "сотрем" все линии, но при этом будем держать в голове, что некоторые люди знают других. Имеем картинку
Рассмотрим случайного человека из 6, например Аню. Разобьем все возможности на 2 случая:
1) Аня знает из 5 оставшихся трех, четырех или всех пятерых человек.
2) Аня знает из 5 оставшихся ноль, одного или двух человек.
В первом случае есть минимум 3 человека, которые соединены с Аней линией. Пусть это будут Вика, Катя и Антон. Давайте рассмотрим их детальнее:
Существует 2 возможных варианта:
1.1) В тройке {Вика, Катя, Антон} никто никого не знает, тогда мы получили требуемую тройку, где никто никого не знает и задача решена.
1.2) В тройке {Вика, Катя, Антон} есть как минимум 1 пара, в которой люди друг друга знают. Пусть друг друга знают Вика и Катя. Но и Катя, и Вика знают Аню, значит в тройке {Вика, Катя, Аня} все знают друг друга и задача решена.
У нас остался случай 2), когда Аня знает из 5 оставшихся ноль, одного или двух человек. В этом случае есть минимум 3 человека, которые НЕ соединены с Аней линией. Пусть это будут все те же Вика, Катя и Антон:
Опять же, имеем 2 возможности:
2.1) В тройке {Вика, Катя, Антон} все друг друга знают, тогда мы получили требуемую тройку, где все друг друга знаюти задача решена.
2.2) В тройке {Вика, Катя, Антон} есть как минимум 1 пара, в которой люди друг друга НЕ знают. Пусть друг друга НЕ знают Вика и Катя. Но и Катя, и Вика НЕ знают Аню, значит в тройке {Вика, Катя, Аня} никто никого не знает и задача решена.
Пишите в комментариях свои соображения по задаче. Расскажите, стоит ли разбирать задачи детальнее, или наоборот, менее детально. У меня для вас есть много сюжетов различной сложности.
Всем спасибо! До новых встреч!