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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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 дают знакомую четвёрку, во втором вместе с С незнакомую. Вуаля