На форуме миста.ру некоторые участники являются друзьями (дружба симметрична). Известно, что ни у каких двух мистян, имеющих одинаковое число друзей на мисте, общих друзей на мисте нет. Обязательно ли найдётся мистянин, у которого ровно один друг на мисте?

оО

ШоЗаХрень?

С тебя штраф за сломанный мозг.

закусывать надо

гений1с, еврейчик, маня? как быть с ними?

у меня воображаемые друзья - Ф, Щ и отбивная с горошком

(0)Необязательно-"некоторые" участники друзьями являются и условие вообще неполное

(7) чей то неполное?

Баян. Решал но забыл.

решается кажись с помощью теории графов, надо вспомнить

Да задача старая.

Ну, из второго утверждения следует вывод - да, найдется.

(12) а почему?

(13) Непересекающиеся подмножества.

(12)Второе утверждение-это (2)"ШизаХрень?"-теперь я понял как решать математические задачи! Ура!

(14) где и кто?

(16) Здесь. Я. :-)

(17) Ну а если серьезно, то я не знаю доказательства. Просто быстрый вывод.

эх вы, давайте рассмотрим мистянина имеющего максимальное число друзей (если таких несколько, то любого из них) и рассмотрим его друзей, что можно сказать о числе друзей у этих друзей? ))

(0) а на поверку-то 99% друзей - ненастоящие!

(19) продолжай

(19)Если взять друзей одного мистянина, то получается что среди них нет друзей, если взять каждого из них , то у них могут быть друзья, но среди этих друзей то же нет друзей, когда все мистяне закончатся, то останется хотя бы 2 мистянина у которых нет общих друзей

(21) с одной стороны у них (друзей максимального, которого выбрали) не менее 1 друга, с другой - у всех разное число. Если у выбранного N, то получается у его друзей (их N) от 1 до N без пропусков. Все

(23) Красиво
Теперь раскрой секрет "Путешествие через пустыню"

(24) там числа с потолка взяты, да и решения я не помню, но общий смысл - строить пирамиду пищевой цепочки, пока она не достигнет нужного размера

(25) я что-то подобное и делал,
но для твоих "цифр с потолка" задача нерешаема на бумаге (более 100 итераций), я думал может там реально формулу вывести

(0) Необязательно. я тут 1

(27) согласен нужно доп.условие, что есть хотя бы одна пара мистян, которые дружат

кто такие мистяне? Я только одного знаю, Волшебник вроде, по-моему.
Остальные так потрындеть

У меня друзья - это мистянки размером бюста больше 3.

(29) да-да http://www.forum.mista.ru/mytopics.php?user_id=1