?

Log in

No account? Create an account
задачка про знакомых - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка про знакомых [дек. 26, 2003|08:01 am]
Anatoly Vorobey
Милая задачка на решение в уме, олимпиадного типа:

На вечеринке несколько человек. Если два человека знакомы, у них нет общих знакомых. Если они не знакомы, у них ровно двое общих знакомых. Доказать, что у всех участников вечеринки одно и то же количество знакомых.


Если кому-то лень думать, то решение есть в журнале ilyavinarsky, которому спасибо за эту задачку.
СсылкаОтветить

Comments:
[User Picture]From: kapahel
2003-12-25 10:32 pm

несколько часов в уме

интересно, что вы пишете, что на решение в уме, а Илья — что несколько часов решал
(Ответить) (Thread)
[User Picture]From: avva
2003-12-25 10:38 pm

Re: несколько часов в уме

С олимпиадными задачками никогда заранее не знаешь. Я её решил минут за 15, но это, наверное, просто потому, что немало таких в своё время нащёлкал. А хорошо подготовленный к олимпиаде высокого уровня старшеклассник решит ещё быстре, думаю.

Не в уме её неинтересно решать, мне кажется, интерес как раз в том, чтобы картинку удержать и распутать в голове.
(Ответить) (Parent) (Thread)
[User Picture]From: kapahel
2003-12-25 10:44 pm

Re: несколько часов в уме

знакомый математик сказал как-то, что подготовка детей к олимпиадам — дрессура, а сами олимпиады — спорт (типа штанги, бессмысленный)
(Ответить) (Parent) (Thread)
[User Picture]From: cema
2003-12-26 02:18 am

Re: несколько часов в уме

Absolutely.
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2003-12-25 10:43 pm

Re: несколько часов в уме

Я не только решением задачки занимался эти несколько часов: развлекал гостей, потом мыл посуду, убирал после детей... потом лёг спать, и придумал решение.
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2004-10-16 10:40 pm

Re: несколько часов в уме

Ну, так то ж Илья, а то - Авва.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-12-25 10:39 pm
Следующие два шага: придумать такую вечеринку с 16 людьми. А потом с 56 людьми.
А уже следующий шаг до сих пор никто не сделал.
(Ответить) (Thread)
[User Picture]From: avva
2003-12-25 10:40 pm
Да? Интересно ;)
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-12-25 10:46 pm
Называется все это - сильно регулярные графы. Обалденной красоты объекты, и неизвестное начинается сразу за порогом.
16 человек правильно перезнакомить нетрудно (но вряд ли удастся в уме:) ). Называется - "граф Клебша".
56 - уже серьезная задача, и получается "граф Гевиртца".
А следующий кандидат, про которого неизвестно, это 352.
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2003-12-25 10:58 pm
Я в уме придумал вечеринку с 4 людьми.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-12-26 12:49 am
Подсказка: 16 - тоже степень двойки :)
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2003-12-26 02:09 am
4-куб с соединенными противоположными вершинами.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-12-26 02:16 am

Поздравляю!
Следующее развлечение: выкинуть одного человека и всех его знакомых; что останется?
(Ответить) (Parent) (Thread)
From: oblomov_jerusal
2003-12-26 03:38 am
Пусть мы удалили вершину (0000) и ее соседей, оставшиеся вершины расположим так.

                (1110)
      (1100)               (0110) 

                (1010)
            (0011)   (0111)
             (0101)(1011)

         (1101)        (1001)

Мы имеем граф из 5-угольника и пятиконечной звезды с соединенными соответствующими вершинами (не помню, чье имя носит этот граф). А есть красивое доказательство этого?
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2003-12-26 03:52 am

называется - граф Петерсена.

Описать его можно, например, так: вершинами будут двухэлементные подмножества мн-ва 12345, а смежными будут не пересекающиеся.
А теперь будем строить наш 16-вершинный граф, начиная с одной вершины Х. У нее 5 соседей: 1,2,3,4,5, и все они незнакомы. Значит, у каждой пары соседей есть еще ровно один общий знакомый, кроме Х. Все они разные, и их как раз 10, и называть мы их будем 12,13,итд. И у каждого мы уже знаем двух соседей, надо найти еще трех - среди этих 10. Но если пары пересекаются, то знакомыми они быть не могут. Значит, только три варианта и остается - ровно столько, сколько надо. Осталось проверить, что если все устроить именно так, то получится то, что надо.
(Ответить) (Parent) (Thread)
[User Picture]From: stas
2003-12-26 08:09 am

Попытка решения

Пишу здесь, чтобы не открывать сообщение у Ильи и не подсмотреть тем самым ответ :)

Возмём двух человек - А и Б.
1. А и Б знакомы. Тогда каждый знакомый Б (ЗБ) не знаком с А. Из этого, у ЗБ есть с А ровно один общий знакомый - ЗА(Б) (т.к. всего их два, и один мы уже знаем - это Б). У разных ЗБ эти знакомые разные - т.к. если ЗА(Б1)=ЗА(Б2), то у этого ЗА есть с Б 3 общих знакомых - Б1, Б2 и А. Разумеется, очевидно, что ни один ЗА(Б) не равен А - в этом случае получился бы "треугольник" из знакомых, что условием запрещено.
Симметрично, та же история с А - у каждого знакомого А есть ровно один знакомый Б, причём все они разные. Таким образом, получаем (это, кажется, теорема Кантора-Бернштейна?), что если А и Б знакомы, то у них равное количество знакомых.
2. А и Б не знакомы. Тогда у них есть общий знакомый X, причём количество знакомых у X и А равны, так же как и у X и Б. Отсюда, у А и Б и в этом случае равное количество знакомых.
(Ответить) (Thread)
[User Picture]From: stas
2003-12-26 08:22 am

Re: Попытка решения

В 1., кажется, не хватает доказательства, что хотя бы один ЗБ, кроме А, существует. Это из того, если на вечеринке больше 2 человек (этот случай, как тривиальный, не рассматриваем), то для каждого В, не равного А, либо он знаком с Б, либо нет - и тогда у Б должно быть с ним 2 общих знакомых, из которых, понятно, как минимум один будет не А.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2003-12-26 08:13 am
Согласительли с решением в словах я положил Ильи ?

Оно очень схоже с вашим, но более прямолинейно, я вижу как 12
летний мог его решить.

Путь - взяли два набора знакомых двух произвольных людей
и показали члены этих группы находятся в взаимооднозначном соотвествии
знакомств друг с другом (у каждого из знакомых А есть
только один знакомый среди знакомых И и наоборот)
Поскольку A и B произвольны - все доказано
(Ответить) (Thread)
From: dmpogo
2003-12-26 08:13 am
Согласительли с решением в словах я положил Ильи ?

Оно очень схоже с вашим, но более прямолинейно, я вижу как 12
летний мог его решить.

Путь - взяли два набора знакомых двух произвольных людей
и показали члены этих группы находятся в взаимооднозначном соотвествии
знакомств друг с другом (у каждого из знакомых А есть
только один знакомый среди знакомых И и наоборот)
Поскольку A и B произвольны - все доказано
(Ответить) (Thread)
[User Picture]From: avva
2003-12-26 01:45 pm
Это решение тоже работает, но я не согласен с тем, что 12-летний мальчик его скорее придумает. Наоборот, моё решение использует один из обычных трюков для решения олимпиадных задач, известных старшеклассникам, которые участвуют в мат. олимпиадах.
(Ответить) (Parent) (Thread)
[User Picture]From: ltwood
2003-12-26 09:06 am

Развлекаться так развлекаться...

http://www.livejournal.com/users/ltwood/3283.html (еще одна задачка, причем, IMHO, гораздо более красивая).
(Ответить) (Thread)
[User Picture]From: avva
2003-12-26 09:15 am

Re: Развлекаться так развлекаться...

Ага, решил вроде. Тоже хорошая задачка, спасибо ;)
(Ответить) (Parent) (Thread)
[User Picture]From: vnarod
2003-12-30 10:21 am

Еще задачка

Мне вот эта понравилась
(Ответить) (Thread)
From: migmit
2012-05-15 06:27 am
Пусть n - число людей на вечеринке. Выберем одного из них, назовём его P, и обозначим через x количество его знакомых.

Посчитаем число способов выбрать людей 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, количество знакомых у него одно и то же.
(Ответить) (Thread)