Матиас:
Я подозреваю, что работает следующий жадный подход: начиная с самой большой группы, возьмите каждую группу и выделите одного человека из этой группы на стол, выбирая первые столы с наибольшим количеством свободных мест.
Действительно. И небольшая вариация аргумента Тклечека доказывает это.
Предположим, что есть решение. Мы должны доказать, что алгоритм находит решение в этом случае.
Это неверно верно, если число групп равно 0.
Для этапа индукции мы должны показать, что, если есть какое-либо решение, есть одно, где один член самой большой группы сидит за каждой из (размер самой большой группы) самых больших таблиц.
Условие L: Для всех пар (T1, T2) таблиц, если T1
Пусть S1 - решение. Если S1 удовлетворяет L, мы закончили. В противном случае существует пара (T1, T2) таблиц с T1 T1, существует группа, в которой член находится в точке T2, но нет члена в точке T1 (или в точке T2 есть свободное место). Таким образом, эти двое могут поменяться местами (или член самой большой группы может переместиться на свободное место в Т2), и мы получаем решение S2 с меньшим количеством пар таблиц, нарушающих L. Поскольку после конечного числа шагов существует только конечное количество таблиц мы нашли решение Sk, удовлетворяющее L.
Гипотеза об индукции: для всех созвездий N групп и всех чисел M таблиц, если решение найдено, алгоритм найдет решение.
Теперь рассмотрим совокупность (N + 1) групп и M таблиц, в которых существует решение. С учетом вышеизложенного также существует решение, в котором члены самой большой группы размещаются в соответствии с алгоритмом. Разместите их так. Это сводит проблему к разрешимому созвездию из N групп и таблиц M ', что решается алгоритмом согласно индукционной гипотезе.