Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I can't seem to figure out a solid way to use math to parse out what I want to accomplish - thank you in advance for help.
I have 30 people who I need to meet over seven different meeting dates. I'd like to have groups of 6 groups of 5 meet each of the seven weeks. Is there a way to produce a meeting chart to allow for the minimal amount over overlap while having each person meet each other?
I have 30 people who I need to meet over seven different meeting dates.
There are some simple calculations that help to sort out what is possible and what isn't, if your goal is "having each person meet each other" in a schedule where each group is of size $k$ and there are $q$ groups that meet each day/week of the schedule.
First $kq$ must be the number of people $v=30$ in your design. Second we see that on any given day, each person will meet $k-1$ other people who happen to be in the same group for that day.
In order for each person to meet all $v-1=29$ other people, we need a schedule of at least $\lceil (v-1)/(k-1) \rceil$ days (rounding up if that quotient isn't an exact integer).
I'd like to have groups of 6 groups of 5 meet each of the seven weeks.
The problem as originally written seemingly has $q=6$ groups of $k=5$ people each day. But then seven days (weeks) are not enough because $\lceil (v-1)/(k-1) \rceil \gt 7$.
Perhaps the wording is slightly garbled and the intent was $q=5$ groups of $k=6$ people each day. In that case seven days will be enough. Each day of meetings allows a person to meet $k-1=5$ other people, and $5\cdot 7 = 35 \gt 29$.
However some people will meet more than once, since $35$ is strictly greater than $29$. This excess (or "overlap" as the Question describes it) can be distributed in a kind of uniform way, though the total of duplicate meetings is not really minimized because it is known in advance.
This uniform way is to treat the $30$ people as $15$ pairs of people. We then assign these pairs of people, three at a time, to $q=5$ groups of $k=6$ people each day so that each pair meets each other pair exactly once during the seven days of the schedule. This amounts to substituting these pairs for the fifteen individuals in Kirkman's schoolgirl problem.
The result is that while partners in a pair will meet in all seven of their scheduled groups, otherwise two people will meet exactly once.
For convenience we list such seven days of five groups (six people in each group), where people are $0$ to $29$ and pairs are $(2n,2n+1)$ for $n=0,\ldots,14$:
Sunday
$ \begin{array}{lrrrrrrr}
(& 0, & 1, & 10, & 11, & 20, & 21 &) \\
(& 2, & 3, & 12, & 13, & 22, & 23 &) \\
(& 4, & 5, & 14, & 15, & 24, & 25 &) \\
(& 6, & 7, & 16, & 17, & 26, & 27 &) \\
(& 8, & 9, & 18, & 19, & 28, & 29 &) \end{array} $
Monday
$ \begin{array}{lrrrrrrr}
(& 0, & 1, & 2, & 3, & 8, & 9 &) \\
(& 4, & 5, & 6, & 7, & 12, &13 &) \\
(& 14, & 15, & 16, & 17, & 22, & 23 &) \\
(& 18, & 19, & 20, & 21, & 26, & 27 &) \\
(& 24, & 25, & 28, & 29, & 10, & 11 &) \end{array} $
Tuesday
$ \begin{array}{lrrrrrrr}
(& 2, & 3, & 4, & 5, & 10, & 11 &) \\
(& 6, & 7, & 8, & 9, & 14, & 15 &) \\
(& 16, & 17, & 18, & 19, & 24, &25 &) \\
(& 20, & 21, & 22, & 23, & 28, &29 &) \\
(& 26, & 27, & 0, & 1, & 12, & 13 &) \end{array} $
Wednesday
$ \begin{array}{lrrrrrrr}
(& 8, & 9, & 10, & 11, & 16, & 17 &) \\
(& 12, & 13, & 14, & 15, & 20, & 21 &) \\
(& 22, & 23, & 24, & 25, & 0, & 1 &) \\
(& 26, & 27, & 28, & 29, & 4, &5 &) \\
(& 2, & 3, & 6, & 7, & 18, &19 &) \end{array} $
Thursday
$ \begin{array}{lrrrrrrr}
(& 4, & 5, & 8, & 9, & 20, & 21 &) \\
(& 6, & 7, & 10, & 11, & 22, & 23 &) \\
(& 12, & 13, & 16, & 17, & 28, & 29 &) \\
(& 14, & 15, & 18, & 19, & 0, & 1 &) \\
(& 24, & 25, & 26, & 27, & 2, & 3 &) \end{array} $
Friday
$ \begin{array}{lrrrrrrr}
(& 8, & 9, & 12, & 13, & 24, & 25 &) \\
(& 10, & 11, & 14, & 15, & 26, & 27 &) \\
(& 16, & 17, & 20, & 21, & 2, & 3 &) \\
(& 18, & 19, & 22, & 23, & 4, & 5 &) \\
(& 28, & 29, & 0, & 1, & 6, & 7 &) \end{array} $
Saturday
$ \begin{array}{lrrrrrrr}
(& 20, & 21, & 24, & 25, & 6, & 7 &) \\
(& 22, & 23, & 26, & 27, & 8, & 9 &) \\
(& 28, & 29, & 2, & 3, & 14, & 15 &) \\
(& 0, & 1, & 4, & 5, & 16, & 17 &) \\
(& 10, & 11, & 12, & 13, & 18, & 19 &) \end{array} $
