задачка про знакомых

[avva]

Милая задачка на решение в уме, олимпиадного типа:

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

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

Comments

[flaass.livejournal.com]

Следующие два шага: придумать такую вечеринку с 16 людьми. А потом с 56 людьми.
А уже следующий шаг до сих пор никто не сделал.

[avva.livejournal.com]

Да? Интересно ;)

[flaass.livejournal.com]

Называется все это - сильно регулярные графы. Обалденной красоты объекты, и неизвестное начинается сразу за порогом.
16 человек правильно перезнакомить нетрудно (но вряд ли удастся в уме:) ). Называется - "граф Клебша".
56 - уже серьезная задача, и получается "граф Гевиртца".
А следующий кандидат, про которого неизвестно, это 352.

[ex-ilyavinar899.livejournal.com]

Я в уме придумал вечеринку с 4 людьми.

[flaass.livejournal.com]

Подсказка: 16 - тоже степень двойки :)

[oblomov-jerusal.livejournal.com]

4-куб с соединенными противоположными вершинами.

[flaass.livejournal.com]

Поздравляю!
Следующее развлечение: выкинуть одного человека и всех его знакомых; что останется?

[oblomov-jerusal.livejournal.com]

Пусть мы удалили вершину (0000) и ее соседей, оставшиеся вершины расположим так.

                (1110)
      (1100)               (0110) 

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

         (1101)        (1001)

Мы имеем граф из 5-угольника и пятиконечной звезды с соединенными соответствующими вершинами (не помню, чье имя носит этот граф). А есть красивое доказательство этого?

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

[flaass.livejournal.com]

Описать его можно, например, так: вершинами будут двухэлементные подмножества мн-ва 12345, а смежными будут не пересекающиеся.
А теперь будем строить наш 16-вершинный граф, начиная с одной вершины Х. У нее 5 соседей: 1,2,3,4,5, и все они незнакомы. Значит, у каждой пары соседей есть еще ровно один общий знакомый, кроме Х. Все они разные, и их как раз 10, и называть мы их будем 12,13,итд. И у каждого мы уже знаем двух соседей, надо найти еще трех - среди этих 10. Но если пары пересекаются, то знакомыми они быть не могут. Значит, только три варианта и остается - ровно столько, сколько надо. Осталось проверить, что если все устроить именно так, то получится то, что надо.