Uоловоломная задачка

[ARBUZ]

Вот ещё головоломная задачка. У-у-у-у-х!

Найти наименьшее значение n , для которого любой коллектив, где каждый недолюбливает не более семи из остальных, можно разбить на не более чем n частей так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого.

[Ольга К]

Source of the post
Вот ещё головоломная задачка. У-у-у-у-х!

Найти наименьшее значение n , для которого любой коллектив, где каждый недолюбливает не более семи из остальных, можно разбить на не более чем n частей так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого.

я думаю, что ответ: 8
докажем что 8 групп достаточно: разместим первые 8 человек по одному в группу. теперь будем размещать каждого следующего человека,у него не больше 7 врагов, поэтому они не более чем в 7 группах и всегда найдется группа в которую его можно поместить
таким образом все люди размещаются в 8 группах.
докажем теперь, что 7 групп недостачно.
рассмотрим 8 человек, каждый из которых недолюбливает 7 остальных. очевидно, их нельзя разместить в 7 групп
может кто-нибудь не согласен?

[Pavlovsky]

может кто-нибудь не согласен?

Bce согласны.

Тогда задачка по сложнее.
Коллектив состоит из N человек. Известно что в любой тройке человек обязательно есть хотя бы одна пара человек не знакомых друг c другом.
Какое максимальное количество пар человек знакомых друг c другом может быть в этом коллективе?
Пример пусть N=4 обозначим людей (A,B,C,D) тогда очевидно max=4
(AC),(AD),(BC),(BD)

[ARBUZ]

Зацените-ка:

He очень чёткие условия. Получается коллектив не любой, a более 10 человек?

Семь остальных, я, восьмой. Люблю семерых. Делю нас на 8, так как пара влюбленных - табу.
Делю на 2. Теперь трое могут любить четвертого.
Двойка меньше восьмерки. n=2.
Ведь не сказано что нельзя более, значит более двоих любить можно. Вот я и поделил.

Рассмотри цитату:
"Найти наименьшее значение n , для которого ЛЮБОЙ коллектив...не более семи...."
Возьмем один конкретный из любых коллективов - числом человек 7, где каждый ненавидит каждого.
Для этого коллектива очевидно число групп=7
Поэтому и ответ (для ЛЮБЫХ коллективов) ограничивается этим числом групп n=7
Поэтому я и сказал что условия не четкие.

Выходит, что n=7.
Может быть, возможно как-нибудь решить, используя теорию вероятностей и комбинаторику?

Ах да и ещё

так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого

Из этого следует, что 1 и 2 нельзя, но ведь больше-то недолюбливающих можно.

[ARBUZ]

Зацените-ка:

He очень чёткие условия. Получается коллектив не любой, a более 10 человек?
Семь остальных, я, восьмой. Люблю семерых. Делю нас на 8, так как пара влюбленных - табу.
Делю на 2. Теперь трое могут любить четвертого.
Двойка меньше восьмерки. n=2.
Ведь не сказано что нельзя более, значит более двоих любить можно. Вот я и поделил.
"Найти наименьшее значение n , для которого ЛЮБОЙ коллектив...не более семи...."
Возьмем один конкретный из любых коллективов - числом человек 7, где каждый ненавидит каждого.
Для этого коллектива очевидно число групп=7
Поэтому и ответ (для ЛЮБЫХ коллективов) ограничивается этим числом групп n=7
Поэтому я и сказал что условия не четкие.
Выходит, что n=7.
Может быть, возможно как-нибудь решить, используя теорию вероятностей и комбинаторику?

Ах да и ещё

так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого

Из этого следует, что 1 и 2 нельзя, но ведь больше-то недолюбливающих можно.