задачка про знакомых
Dec. 26th, 2003 08:01 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaМилая задачка на решение в уме, олимпиадного типа:
Если кому-то лень думать, то решение есть в журнале![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
ilyavinarsky, которому спасибо за эту задачку.
На вечеринке несколько человек. Если два человека знакомы, у них нет общих знакомых. Если они не знакомы, у них ровно двое общих знакомых. Доказать, что у всех участников вечеринки одно и то же количество знакомых.
Если кому-то лень думать, то решение есть в журнале
ilyavinarsky, которому спасибо за эту задачку.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
несколько часов в уме
Date: 2003-12-25 10:32 pm (UTC)Re: несколько часов в уме
Date: 2003-12-25 10:38 pm (UTC)Не в уме её неинтересно решать, мне кажется, интерес как раз в том, чтобы картинку удержать и распутать в голове.
Re: несколько часов в уме
Date: 2003-12-25 10:44 pm (UTC)Re: несколько часов в уме
Date: 2003-12-26 02:18 am (UTC)Re: несколько часов в уме
Date: 2003-12-25 10:43 pm (UTC)Re: несколько часов в уме
Date: 2004-10-16 10:40 pm (UTC)no subject
Date: 2003-12-25 10:39 pm (UTC)А уже следующий шаг до сих пор никто не сделал.
no subject
Date: 2003-12-25 10:40 pm (UTC)no subject
Date: 2003-12-25 10:46 pm (UTC)16 человек правильно перезнакомить нетрудно (но вряд ли удастся в уме:) ). Называется - "граф Клебша".
56 - уже серьезная задача, и получается "граф Гевиртца".
А следующий кандидат, про которого неизвестно, это 352.
no subject
Date: 2003-12-25 10:58 pm (UTC)no subject
Date: 2003-12-26 12:49 am (UTC)no subject
Date: 2003-12-26 02:09 am (UTC)no subject
Следующее развлечение: выкинуть одного человека и всех его знакомых; что останется?
no subject
Date: 2003-12-26 03:38 am (UTC)(1110) (1100) (0110) (1010) (0011) (0111) (0101)(1011) (1101) (1001)Мы имеем граф из 5-угольника и пятиконечной звезды с соединенными соответствующими вершинами (не помню, чье имя носит этот граф). А есть красивое доказательство этого?
называется - граф Петерсена.
Date: 2003-12-26 03:52 am (UTC)А теперь будем строить наш 16-вершинный граф, начиная с одной вершины Х. У нее 5 соседей: 1,2,3,4,5, и все они незнакомы. Значит, у каждой пары соседей есть еще ровно один общий знакомый, кроме Х. Все они разные, и их как раз 10, и называть мы их будем 12,13,итд. И у каждого мы уже знаем двух соседей, надо найти еще трех - среди этих 10. Но если пары пересекаются, то знакомыми они быть не могут. Значит, только три варианта и остается - ровно столько, сколько надо. Осталось проверить, что если все устроить именно так, то получится то, что надо.
Попытка решения
Date: 2003-12-26 08:09 am (UTC)Возмём двух человек - А и Б.
1. А и Б знакомы. Тогда каждый знакомый Б (ЗБ) не знаком с А. Из этого, у ЗБ есть с А ровно один общий знакомый - ЗА(Б) (т.к. всего их два, и один мы уже знаем - это Б). У разных ЗБ эти знакомые разные - т.к. если ЗА(Б1)=ЗА(Б2), то у этого ЗА есть с Б 3 общих знакомых - Б1, Б2 и А. Разумеется, очевидно, что ни один ЗА(Б) не равен А - в этом случае получился бы "треугольник" из знакомых, что условием запрещено.
Симметрично, та же история с А - у каждого знакомого А есть ровно один знакомый Б, причём все они разные. Таким образом, получаем (это, кажется, теорема Кантора-Бернштейна?), что если А и Б знакомы, то у них равное количество знакомых.
2. А и Б не знакомы. Тогда у них есть общий знакомый X, причём количество знакомых у X и А равны, так же как и у X и Б. Отсюда, у А и Б и в этом случае равное количество знакомых.
Re: Попытка решения
Date: 2003-12-26 08:22 am (UTC)no subject
Date: 2003-12-26 08:13 am (UTC)Оно очень схоже с вашим, но более прямолинейно, я вижу как 12
летний мог его решить.
Путь - взяли два набора знакомых двух произвольных людей
и показали члены этих группы находятся в взаимооднозначном соотвествии
знакомств друг с другом (у каждого из знакомых А есть
только один знакомый среди знакомых И и наоборот)
Поскольку A и B произвольны - все доказано
no subject
Date: 2003-12-26 08:13 am (UTC)Оно очень схоже с вашим, но более прямолинейно, я вижу как 12
летний мог его решить.
Путь - взяли два набора знакомых двух произвольных людей
и показали члены этих группы находятся в взаимооднозначном соотвествии
знакомств друг с другом (у каждого из знакомых А есть
только один знакомый среди знакомых И и наоборот)
Поскольку A и B произвольны - все доказано
no subject
Date: 2003-12-26 01:45 pm (UTC)Развлекаться так развлекаться...
Date: 2003-12-26 09:06 am (UTC)Re: Развлекаться так развлекаться...
Date: 2003-12-26 09:15 am (UTC)Еще задачка
Date: 2003-12-30 10:21 am (UTC)no subject
Date: 2012-05-15 06:27 am (UTC)Посчитаем число способов выбрать людей A, B и C, так, чтобы A и B были знакомы с P и C (и при этом A, B, C и P были разными людьми).
Попробуем сначала выбрать C. Это должен быть человек, отличный от P, и не знакомый с ним (так как у них должны найтись общие знакомые). Если мы выберем такого человека, то у них с P ровно два общих знакомых, так что одного из них (любого) надо назначить на роль A, а другого - на роль B. Таким образом, число способов выбрать такую тройку будет равно 2(n-x-1).
С другой стороны, мы можем сначала выбрать A и B среди знакомых P. У них будет общий знакомый (P), и, значит, они не будут знакомы друг с другом. Тогда у них будет ещё ровно один общий знакомый, которого придётся назначить на роль C. Значит, число способов выбрать такую тройку A, B, C будет равно x(x-1).
Остальное тривиально: x^2-x=2(n-x-1), x^2+x-2(n-1)=0, у этого уравнения не более одного положительного корня, значит, n однозначно определяет x, то есть, какого бы человека мы ни взяли на роль P, количество знакомых у него одно и то же.