Здравствуйте, nikholas, Вы писали:

N>В компании работает 18 человек.
N>Доказать, что существуют четверо попарно знакомых (каждый с каждым), либо четверо попарно незнакомых.

Имхо вариация теоремы Рамсея.

Здравствуйте, nikholas, Вы писали:

N>В компании работает 18 человек.
N>Доказать, что существуют четверо попарно знакомых (каждый с каждым), либо четверо попарно незнакомых.

Хорошая задача.
Широко известна её младшая сестра про группу из 6-ти человек.
Там всегда найдётся либо тройка знакомых либо тройка незнакомых.
(Прочитать можно например здесь)

Выберем одного человека. Кроме него в компании ещё 17. Это значит, что либо есть 9, с которыми он знаком, либо 9, с которыми не знаком. Без ограничения общности можно считать что первое (если второе, везде ниже ставим/убираем 'не').

Итак у нас есть один человек (A) и 9 с ним знакомых. Выберем среди этих 9-ти любого (B). Если у него есть среди оставшихся 8-ми 4 знакомых, то всё доказано — либо хоть одна пара из этих 4-х знакома и они вместе с A и B дают "знакомую" четвёрку, либо никто из этих 4-х друг с другом не знаком и они дают "незнакомую" четвёрку.

Значит в группе из 9 человек каждый знаком не более чем с 3-мя другими. Однако не может быть такого, что каждый знаком ровно с 3-мя. Дело в том, что если каждый из 9-ти знаком ровно с тремя, то попарных связей должно быть 9*3/2=13.5 т.е. нецелое число. Значит хотя бы один из 9-ти (С) знаком не более чем с 2-мя.

Выберем группу из тех 6-ти, с которыми C не знаком. По известной задаче в любой группе из 6-ти человек есть либо трое знакомых либо трое незнакомых. В первом случае эти трое вместе с A дают знакомую четвёрку, во втором вместе с С незнакомую. Вуаля

Здравствуйте, m.a.g., Вы писали:

Мда... ну и тема у вашего ответа....

В компании работает 18 человек.
Доказать, что существуют четверо попарно знакомых (каждый с каждым), либо четверо попарно незнакомых.

Здравствуйте, m.a.g., Вы писали:

MAG>Здравствуйте, nikholas, Вы писали:

N>>В компании работает 18 человек.
N>>Доказать, что существуют четверо попарно знакомых (каждый с каждым), либо четверо попарно незнакомых.

MAG>Имхо вариация теоремы Рамсея.

Замечательно, но я ничего не понял

MAG>Имхо вариация теоремы Рамсея.

Я бы посоветовал выясняться по ясней.
Если следовать вашему примеру то ответ типа: ето вариационное счисление с применением биномиального распределения тоже должен устроить но не мне вам говорить что за маразм тут написан.

Здравствуйте, arabo_xv, Вы писали:

MAG>>Имхо вариация теоремы Рамсея.

Теорема Рамсея конечно неизвестно что, но постановка задачи не ахти.

Как я понял если люди раьботают вместе, то они обязательно кто-то кого-то знают.

Есть нет четверо попарно знакомых или не знакомых. Значит есть или только пары знакомых, но тогда цепочка распадёться или тройки.

Для троек максимальное число людей где нет 4-ки попарно незнакомых вроде бы 6. Вроде бы уже среди 7 найдёться хоть какая-то (знакомых или не знакомых) четвёрка.

Но за постановку условия конечно 2- Можно бы и по подробнее....

Здравствуйте, arabo_xv, Вы писали:

MAG>>Имхо вариация теоремы Рамсея.

_>Я бы посоветовал выясняться по ясней.

Я бы посоветовал подновить знание дискретной математики...

Здравствуйте, LCR, Вы писали:

MAG>>Имхо вариация теоремы Рамсея.

LCR>Замечательно, но я ничего не понял

Сие означает, что задача решается исключительно муторным перебором, сложность которого резко возрастает с ростом числа "попарно знакомых". Настолько резко, что для чисел порядка 10 (точно не скажу, но не более 15) эта задача не будет решена никогда. По крайней мере, так сейчас считают.