Знакомые

[Илья]

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

[Virtus]

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

[Кадила???]

Virtus

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

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

[kambodja]

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

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

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

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

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

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

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

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

[iPhonograph]

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

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


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

[kambodja]

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

[buka]

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

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

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

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

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

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

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

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

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

[buka]

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

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


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

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

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

[iPhonograph]

для 2 это как?

[buka]

для 2 это как?

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

[iPhonograph]

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

[buka]

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

Ваше требование резонно. Более того - свято!
//текст доступен после регистрации// и понял, что они ошиблись. Они не доказали того, что хотели!
Более того! Вряд ли докажут

[iPhonograph]

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

[buka]

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

Я могу доказать, что для 7-ми невозможно.
При числе большем семи - тоже невозможно, но доказывать дольше...
Жаль, что Вы не можете открыть ту ссылку...
Попробуйте так: //текст доступен после регистрации//

[Илья]

Я могу доказать, что для 7-ми невозможно.

А как же это:

При n=5 - невозможно (как и при n = 3, 6, 8...). А вот n=1,2,4,7,11 - возможно.