спланировать обучение, деление на группы

[homo sapiens]

Помогите, плиз!

Я не математик, случайно забрела на ваш форум. А задачку решить надо. Задачка из жизни. Нужно спланировать обучение таким образом: 23 человека делятся на 2 группы (например, по 11 и 12
человек). Им предстоит пройти 9 занятий (учатся они отдельно, по времени - условно параллельно). Нужно делать такую рокировку людьми между этими 2-мя группами, чтобы в течение 9-ти занятий каждый участник с каждым участником попадал в группу примерно одинаковое количество раз. Перемешивать их нужно как-то системно, чтобы каждый имел возможность поработать на занятиях со всеми по очереди, а не оказывался все время с одними и теми же!

Извините, четче объяснить не могу.

[PAV]

Хорошая задача. Интересная. Никто не может подсказать, к какой области относится?
Мне кажется, что это что-то из теории расписаний... Также похоже на блок-схемы.

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

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

[незваный гость]

Если количество участников $2^m$, то $m$ раундов можно было бы организовать по-битно: присвоить участникам номера от $0$ до $2^m-1$, и раунде $k$ отправлять участника группы в первую команду, если $k$-ая цифра в двоичном представлении номера участника равна $0$. К сожалению, не работает в условиях задачи.

А вообще, вопрос - требуется ли одноразовое решение (откель и цифры), или цифры лишь для примера? Что Вы скажете, homo sapiens humanitas? Алгоритм может и не сразу подобраться, а чисто конкретный ответ можно и подобрать.

P.S. В алгоритме (выше) я слегка проврался. Например, для четырех участников минимальное количество занятий - три, а алгоритм дает два. Участники "ноль" и "три" никогда не встретятся.

[незваный гость]

PAV писал(а):

Хорошая задача. Интересная. Никто не может подсказать, к какой области относится?

Скорее, при любом раскладе, к Computer Science. Там есть очень странные разделы, например коды Грея.

PAV писал(а):

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

Тут какие-то еще условия нужны. Иначе, на первом же занятии - всех в первую группу, и - опаньки.

Если добавить требование деления пополам - то очевидная оценка снизу $3$. Мы рассматриваем $n > 2$. Тогда условие "каждый с каждым" требует $\frac{n(n-1)}{2}$ дуг, а в пределах каждой из групп реализуется $\frac{(n/2)((n/2)-1)}{2}$. То есть, необходимо по крайней мере $\frac{\frac{n(n-1)}{2}}{2 \frac{n/2(n/2-1)}{2}}=2+\frac{2}{n-2}$. Ну, и поскольку число занятий - число целое, то $3$. (Все вышеприведенное слегка упрощено, реально надо рассматривать отдельно четные и нечетные $n$, но ответ от этого не меняется.) Оценка, вполне вероятно, весьма заниженная. Оценка сверху - $\lceil\log_{2}{n}\rceil$+1, базируется на приведенном в предыдущем сообщении частном случае $n=2^k,\ k \in \mathbb N$. Строго не доказывал, но кажется правдоподобной.

[незваный гость]

PAV писал(а):

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

Мы уже видели (предыдущее сообщение), что оценка снизу - 3. Докажем теперь, что при $n \in \{4 k, 4 k + 1, 4 k + 3 \colon k \in \mathbb N \}$ достаточно трех раундов. Действительно, разделим произвольным образом на группы A, B, C, D каждая из которых состоит из либо $k$, либо $k + 1$ участников. Тогда $A \cup B, C \cup D$; $A \cup C, B \cup D$; и $A \cup D, B \cup C$ задают необходимые составы групп.

При $n \in \{4 k + 2\colon k \in \mathbb N \}$ трех раундов недостаточно, если мы не разрешаем количеству участников группы различаться на два (при этом ослабленном условии алгоритм выше работает). Без ограничения общности, в первом раунде первая группа состоит из участников $1 .. 2 k + 1$, а вторая - $2 k + 2 .. 4 k + 2$. Будем и далее называть первой группой ту, в которую входит участник 1. В двух оставшихся раундах в первую группу должны попасть $2 k + 1$ участника группы два первого раунда. Это значит, что по крайней мере $k + 1$ попадают в первую группу в один из раундов. Без ограничения общности, называем его раунд два. Тогда в раунде два столько же участников группы один первого раунда попадают в группу два. Мы имеем $2 k + 2$ участников, не всречавшихся друг с другом ни в раунде один, ни в раунде два. Но мы не можем поместить их в одну группу в третьем раунде, поскольку их больше, чем размер группы.

Четырех раундов достаточно и этом случае ($n \in \{4 k + 2\colon k \in \mathbb N \}$). Дабы доказать сей удивительный факт, разобьем всех участников на группы A, B, C, D, E, F размером $k$, $k+1$, $1$, $k-1$, $1$, $k$ соответственно. Тогда $A \cup B, C \cup D \cup E \cup F$; $A \cup C \cup D \cup E, B \cup F$; $A \cup C \cup F, B \cup D \cup E$; $A \cup E \cup F, B \cup C \cup D$ задают искомое разбиение на группы. (Поелику D никогда не бывает одна, пустота ее при $n = 6$ неудобств не вызывает.)

Весьма аналогично, кстати, доказывается, что если требовать только чтобы в каждом раунде каждая из групп была непуста, то требуется минимум три раунда. Это заметное ослабление условия из предыдущего сообщения.

~~~~~~

К сожалению, это мало отвечает на вопрос homo sapiens. В пределах одной группы (например, A), участники встречаются во всех трех-четырех раундах, в то время как всегда существуе группа товарищей (например B), с которыми они встречаются лишь однажды.

Однако опять думать надо.