Вот ещё головоломная задачка. У-у-у-у-х!
Найти наименьшее значение n , для которого любой коллектив, где каждый недолюбливает не более семи из остальных, можно разбить на не более чем n частей так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого.
Uоловоломная задачка
Uоловоломная задачка
Последний раз редактировалось ARBUZ 30 ноя 2019, 14:11, всего редактировалось 1 раз.
Причина: test
Причина: test
Uоловоломная задачка
ARBUZ писал(а):Source of the post
Вот ещё головоломная задачка. У-у-у-у-х!
Найти наименьшее значение n , для которого любой коллектив, где каждый недолюбливает не более семи из остальных, можно разбить на не более чем n частей так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого.
я думаю, что ответ: 8
докажем что 8 групп достаточно: разместим первые 8 человек по одному в группу. теперь будем размещать каждого следующего человека,у него не больше 7 врагов, поэтому они не более чем в 7 группах и всегда найдется группа в которую его можно поместить
таким образом все люди размещаются в 8 группах.
докажем теперь, что 7 групп недостачно.
рассмотрим 8 человек, каждый из которых недолюбливает 7 остальных. очевидно, их нельзя разместить в 7 групп
может кто-нибудь не согласен?
Последний раз редактировалось Ольга К 30 ноя 2019, 14:11, всего редактировалось 1 раз.
Причина: test
Причина: test
Uоловоломная задачка
может кто-нибудь не согласен?
Bce согласны.
Тогда задачка по сложнее.
Коллектив состоит из N человек. Известно что в любой тройке человек обязательно есть хотя бы одна пара человек не знакомых друг c другом.
Какое максимальное количество пар человек знакомых друг c другом может быть в этом коллективе?
Пример пусть N=4 обозначим людей (A,B,C,D) тогда очевидно max=4
(AC),(AD),(BC),(BD)
Последний раз редактировалось Pavlovsky 30 ноя 2019, 14:11, всего редактировалось 1 раз.
Причина: test
Причина: test
Uоловоломная задачка
Зацените-ка:
Может быть, возможно как-нибудь решить, используя теорию вероятностей и комбинаторику?
Ах да и ещё
Из этого следует, что 1 и 2 нельзя, но ведь больше-то недолюбливающих можно.
Выходит, что n=7.He очень чёткие условия. Получается коллектив не любой, a более 10 человек?
Семь остальных, я, восьмой. Люблю семерых. Делю нас на 8, так как пара влюбленных - табу.
Делю на 2. Теперь трое могут любить четвертого.
Двойка меньше восьмерки. n=2.
Ведь не сказано что нельзя более, значит более двоих любить можно. Вот я и поделил.
Рассмотри цитату:
"Найти наименьшее значение n , для которого ЛЮБОЙ коллектив...не более семи...."
Возьмем один конкретный из любых коллективов - числом человек 7, где каждый ненавидит каждого.
Для этого коллектива очевидно число групп=7
Поэтому и ответ (для ЛЮБЫХ коллективов) ограничивается этим числом групп n=7
Поэтому я и сказал что условия не четкие.
Может быть, возможно как-нибудь решить, используя теорию вероятностей и комбинаторику?
Ах да и ещё
так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого
Из этого следует, что 1 и 2 нельзя, но ведь больше-то недолюбливающих можно.
Последний раз редактировалось ARBUZ 30 ноя 2019, 14:11, всего редактировалось 1 раз.
Причина: test
Причина: test
Uоловоломная задачка
Зацените-ка:
Ах да и ещё
Из этого следует, что 1 и 2 нельзя, но ведь больше-то недолюбливающих можно.
He очень чёткие условия. Получается коллектив не любой, a более 10 человек?
Семь остальных, я, восьмой. Люблю семерых. Делю нас на 8, так как пара влюбленных - табу.
Делю на 2. Теперь трое могут любить четвертого.
Двойка меньше восьмерки. n=2.
Ведь не сказано что нельзя более, значит более двоих любить можно. Вот я и поделил.
"Найти наименьшее значение n , для которого ЛЮБОЙ коллектив...не более семи...."
Возьмем один конкретный из любых коллективов - числом человек 7, где каждый ненавидит каждого.
Для этого коллектива очевидно число групп=7
Поэтому и ответ (для ЛЮБЫХ коллективов) ограничивается этим числом групп n=7
Поэтому я и сказал что условия не четкие.
Выходит, что n=7.
Может быть, возможно как-нибудь решить, используя теорию вероятностей и комбинаторику?
Ах да и ещё
так, чтобы ни в какой части не нашлось двух человек, хотя бы один из которых недолюбливает другого
Из этого следует, что 1 и 2 нельзя, но ведь больше-то недолюбливающих можно.
Последний раз редактировалось ARBUZ 30 ноя 2019, 14:11, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 5 гостей