Форум умных людей

Собралось n человек. Некоторые из них знакомы между собой, причём каждые два незнакомых имеют ровно двух общих знакомых, а каждые два знакомых не имеют общих знакомых. Доказать, что каждый из присутствующих знаком с одинаковым числом человек.

"Трудное - то, что можно сделать немедленно. Невозможное - то, для выполнения чего требуется немного больше времени."
Это невозможно

Virtus

Сообщений: 5
-вас поблагодарили: 5

Удивительно полезный форумчанин  :peace:

это утверждение неверно.

Рассмотрим простейший случай (проще всего на бумажке нарисовать квадратик-граф, и каждая вершина квадратика - человек) - 4 человека А,Б,В,Г.

А знаком с Б и В, незнаком с Г. Г знаком так же с Б и В. Условие выполняется. Однако добавляем пятого человека - Д.

(пририсуем рядом с квадратиком точку Д)

Нарисуем связи от Д к вершинам графа А и Г.

Все условия на данном графе будут выполнятся - знакомые будут не иметь общих знакомых, незнакомые будут иметь двух общих знакомых.

вот только у А и Г будет трое знакомых, а у Б, В и Г - только двое.

Следовательно, утверждение не верно. Присутствующие будут знакомы с разным количеством человек.

каждые два незнакомых имеют ровно двух общих знакомых


а вот может ли быть n>4, я до сих пор понять не могу...

о чем я и говорю. при n = 4 условия выполняются. но только при 4. при пяти - уже количество знакомых разное при выполнении условий.

В приведённом Вами примере у А и Г, не знакомых между собой будут 3 ОБЩИХ знакомых - Б,В и Д

При n=5 - невозможно (как и при n = 3, 6, 8...). А вот n=1,2,4,7,11 - возможно.
Общий вид для n: n = 1 + к + к(к-1)/2  (к = 0,1,2...)

для 2 это как?

"Каждые" имеется ввиду и пустое множество.
А и Б знакомы между собой и не имеют общих знакомых.
Каждые два не знакомых между собой (в данном случае таковых - ноль) имеют двух общих знакомых...
Задача без деградации абстракции начинается с 4-х.

угу, про двойку понял
теперь хочу понять про семёрку

Ваше требование резонно. Более того - свято!
Я нашёл разбор этой задачи (http://www.problems.ru/view_problem_details_new.php?id=78236) и понял, что они ошиблись. Они не доказали того, что хотели!
Более того! Вряд ли докажут :)

ваша ссылка не открывается
начертить граф для 7 знакомых у меня не получается, расскажите как вам это удалось

Я могу доказать, что для 7-ми невозможно.
При числе большем семи - тоже невозможно, но доказывать дольше...
Жаль, что Вы не можете открыть ту ссылку...
Попробуйте так: http://www.problems.ru/view_problem_details_new.php?id=78236

А как же это:

Очень просто. Сначала я думал, что для 7-ми возможно, потом понял, что невозможно.

Понятно. :)

2 буко
вижу, задачку вы решали гуглем, а гугль подложил вам свинку :)

ссылка открылась
доказательство у них правильное.  оно состоит в том, что если у кого-то М знакомых, то зная М можно вычислить общее количество народа, значит М у всех одно и то же.

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

так что вопрос N>4 остаётся открытым

Хы...  для n=16 граф есть

1. Я поражён Вашим безапелляционным зрением. Вы правильно увидели, что если я решал эту задачу, то гуглем. Но если Вы увидели, что я решал эту задачу, то поделитесь своей исключительной способностью зрения.
2. Всё, что они доказали - это: если для некоторой группы людей работают все перечисленные ими условия, то каждый из них должен быть знаком с одинаковым кол-вом людей и общее число людей связано с кол-вом знакомых для одного человека приведённой ими формулой. Вопрос о том, а существует ли вообще хоть какая-то группа людей, для которых выполняются данные ими условия ими не рассматривался...
На их счастье, такая группа (по крайней мере, одна - таки существует)...
Можно ли принять такое доказательство? Возможно - да. Но тогда и следующее "доказательство" должно быть признано приемлемым:
Чтобы А^5 + В^5 было равно С^5, при целых А,В,С необходимо, чтобы число нечётных среди А,В,С было чётным.
Само "тело" этого "доказательства" я опущу ввиду тривиальности. Но Вы же должны согласиться, что данное утверждение верно и доказать его - плёвое дело. А то, что не рассматривается возможность существования таких соотношений вообще - мелочь, неправда? Ну не повезло мне, что таких А,В,С вообще не существует, а им - повезло, хоти ни я, ни они, не доказывали существование совокупности сформулированных правил вообще...
3. Проверьте ещё раз Ваш граф на 16 (5 знакомых, как я понял)

Так компьютер наверняка помог.

Так если он помог построить, то он поможет и проверить :)

То есть комп мог ошибиться? :)

Комп выполняет то, что ему задают...

Вообщем проверка точно не помешает. :read:

не, без компа построил!

итак, есть 16 человек:
x,
a₁, a₂, a₃, a₄, a₅,
b₁₂, b₁₃, ..., b₄₅ (все возможные пары цифр от 1 до 5)

список всех знакомств (если в списке нет, то не знакомы):
x знаком со всеми a₁..a₅
a_k знаком с b_kj (j,k - это любые 2 разных числа)
b_ij знаком с b_kl (i,j,k,l - это любые 4 разных числа)

проверьте - вроде всё выполняется