Generating rotating groups for a seminar

Question

One of my teachers is planning a seminar for his English class and he asked me if there was a way to generate the groups for the days other than brute-force random generating. I really think there should be a way, but I can't think of something.

Here is the situation:

• There are 18 kids and 22 days
• Each seminar has a group of 12 and a group of 6
• Goals:
  • Maximize the variety of students in groups (i.e. that aren't always in the same or nearly same group of people)
  • Ensure all students are in the second group the same amount $\pm 1$ times

I was hoping to find a way of solving the problem instead of find just a solution. Basically I have two questions:

1. Does anyone know how this can be done?
2. Does anyone have any resources/similar problems/methods that I can look at that might help me solve this?

Answer 1

When I was young I caused problems for my English teachers so I think now is time to thenk them. :-)

Maximize the variety of students in groups (i.e. that aren't always in the same or nearly same group of people)

A straightforward measure of the variety of students in groups $G_1$ and $G_2$ is the size of their intersection $G_1\cap G_2$. Since the big groups are the complements to the small groups, (for both goals) it suffices to deal only with the small groups. So, given $d$ ($22$) days, for the first goal we want to minimize

$$s=1+\max\{|G_i\cap G_j|: 1\le i<j\le d\}.$$

That is no subset of $s$ students can belong to distinct (small) groups. If we have $n$ ($18$) students then there are ${n\choose s}$ such subsets. On the other hand, each of $d$ groups of size $k$ ($6$) provides ${k\choose s}$ such subsets, and all of them are distinct. So we have $d{k\choose s}\le {n\choose s}$, which implies that for our situation $s\ge 3=t$.

We can try to achieve the first goal by taking a part of a Steiner system $S(t,k,n)$. Unfortunately, in our case $(t,k,n)=(3,6,18)$, and the respective Steiner system does not exist, because $b$ is not integer. I tried to recall a combinatorial design with $18$ base elements, which can be used to create a seminar schedule, but I failed.

So I used geometric imagination and constructed a schedule for $24$ days where the students are represented by edges and faces of the cube. The first $12$ days are represented by pairs of adjacent faces of the cube and a schedule for each day is a union of two day’s faces and four edges which are incident to exactly one vertex of these faces. The second $8$ days are represented by vertices of the cube and a schedule for each day is a union of edges and faces incident to day’s vertex. The last $4$ days are represented by pairs of opposite vertices of the cube and a schedule for each day consists of six edges which constitute a cycle not containing day’s vertices. This schedule is balanced, that is each student participates in exactly $8$ (small) groups. So to achieve the second goal it suffices to remove from this schedule two days with disjoint schedules. Such schedules can be taken as corresponding to opposite vertices from the second $8$ days.