Прочее образование

Нужен совет по решению задачи...

Имеется 16 потенциальных сотрудника. Каждый сотрудник враждует с 2 другими сотрудниками (взаимно).
1) Задача состоит в том что бы собрать максимально большую команду, с не враждующими сотрудниками.
2) Собрать вторую другую такую же команду, но с другим составом (возможно с меньшей численностью сотрудников)
Как бы это легко решить?
Ирина Янкулова
Ирина Янкулова
585
Я приведу свои мысли на этот счёт. Возможно, есть другие соображения, позволяющие строго доказать всё нижеприведенное.

Сотрудников всегда можно объединить в "замкнутые" группы, в которых они враждуют попарно "по кругу".
Например, возможна группа из трёх человек, в которой 1-й враждует со 2-м, второй с 3-м, а 3-й с 1-м.
Очевидно также, что "незамкнутых" групп быть не может.
Возможны всего 15 вариантов комбинаций количества человек в таких группах.

3-3-3-3-4, 3-3-3-7, 3-3-4-6, 3-3-5-5, 3-4-4-5, 3-5-8, 3-6-7, 4-4-4-4, 4-5-7, 4-6-6, 5-5-6, 6-10, 7-9, 8-8, 16.

Далее, если количество человек во всех группах чётное, то всегда можно собрать две команды по 8 человек. И бОльшую команду при этом собрать нельзя. Так как выбирать "не враждующих" из каждой группы придётся "через одного", то в случае нечётного кол-ва человек в группе результат будет ещё хуже: не получится сделать менее трёх команд. В худшем случае, насколько я понимаю, получается 4 команды (если, конечно, стараться минимизировать число команд).

Доказать, что 8 - максимум, попробую так: Предположим, мы собрали команду из 8 не враждующих между собой человек. Каждый из них обязательно враждует с двумя людьми из оставшихся восьми. Количество враждебных связей, направленных в оставшуюся группу равно 16. Но кол-во таких связей во второй группе то же, значит во второй группе нет враждующих между собой людей. При переходе одного человека из одной команды в другую этот баланс нарушается. 18 против 14. То есть на команду из 9 чел не хватит врагов во второй команде.
ВС
Владимир Стафикопуло
49 095
Лучший ответ
Ирина Янкулова Убедительно.
Но я решил задачу.
так как я не мог представить как её решать. я сделал так
нарисовал 4 столбика))
и наугад взял одного сотрудника (№1) и записал в 1 столбик.
Его двух недругом (№2 и №3) записал во 2 ст.
потом по очереди разобрался с №2 и №3.
Стал записывать их недругов - оказалось по одному тк №1 уже не в счет.... и тд
В итоге у меня 2 столбика по 3 человека и 2 столбика по 5.
следовательно 1 столбик со 2 враждует. И 3 со 4 аналогично
Ирина Янкулова следовательно я могу воспользоваться 4 максимальными командами на мое усмотрение
первая- сотрудники с 1 столбика и 3
вторая сотрудники с 2 столбика и 4
третья 1 с 4
четвертая 2 с 3
Владимир Стафикопуло Строго говоря, вариантов групп несколько больше. Задача, собственно, решена, но справедливости ради, добавлю недостающие варианты для тех, кто, возможно, воспользуется ответом в будущем.

3-3-10, 3-4-9, 3-13, 4-4-8, 4-12, 5-11. Вроде всё.
1) два человека. потому что третий буде враждовать с первыми двумя
Мария Владимировна
Мария Владимировна
468
Владимир Стафикопуло Автору вопроса:
1) По какому предмету эта задача?
2) Мы знаем точно, кто конкретно с кем враждует?

Похожие вопросы