A combinatorial problem

A colleague of mine had to arrange his students into groups of 3 (let us assume there are 3n students to begin with). At each new session he would have to randomly generate new groups. So far this is not difficult, but the students complained that they often ended up in the same group. So there is now a constraint : each given couple of students cannot be in the same group more than once.

In order to be clear let us say that a 3-partition is a partition of the 3n students into n groups of 3 students.

The problem is to find a way to generate the longest possible sequence of 3-partition such that no couple of students lies in the same group more than once. This looked simple at first, but I could not solve it. I order to understand the complexity of it you have to play around with some examples.

For n=1 there is obviously only one possible 3-partition. For n=2, say you first partition the students like this : (123)(456). It takes little time to realize than it is not possible to find a second 3-partition satisfying the constraint. Indeed, students 1,2 and 3 have to fall in 3 different groups and there are only 2 of them !

For n=3 I let you work a little bit to find a sequence of 4 admissible 3-partition. Hence if there are 12 students, my colleague will be able to run 4 sessions in a row without the students complaining !

Is 4 optimal ? Yes, it is. If the students are numbered 1,2,...,9, then student 1 will be successively with 2 different students in each session, that is 8 other students. Since no other student is available, there cannot be a fifth session. Generalizing this reasoning sets an upper bound to the length of the sequence : E((3n-1)/2), where E is the integer part.

I found a way to realize this optimum if n is a power of 3. In that case, we can imagine that the students are the points in the affine space V=(Z/3Z)^k, where 3n=3^k. The groups of 3 students will be parallel lines, and a 3-partition will be a partition of V into parallel lines. It is not difficult to count them (there are 1+3+...+3^(k-1) of them, which is precisely (3n-1)/2) and show that they satisfy the constraint. However the general case seems much more difficult.

In the case n=4 I have convinced myself that one cannot continue the following sequence of 3-partitions :

(123) (456) (789) (10 11 12)

(9 1 11) (12 4 2) (3 7 5) (6 10 8)

(5 9 10) (8 12 1) (11 3 4) (2 6 7)

I case you wonder how I found it, try to look at the pattern formed by 1, 2 and 3 in the second row : I have sent 1, which was at the first position in the first group, in the first group but in second position, 2 in the second group third position, 3 in the third group third position. Similarly if (a_0 a_1 a_2) is my group number k then I send a_0 in the group k at position 2, a_1 in group k+1 mod 4 at position 3 and a_2 in group k+2 mod 4 at position 1. This trick can be used for any n>3 but unfortunately only provides sequences of 3 admissible 3-partitions.

However, even if this sequence cannot be continued, I could not prove that no longer sequence exists. Can you ?

Finally, here is another simple trick : if (a_0 a_1 a_2) is the k-th group in some row, then in the next row you can send a_0 in the k-th group, a_1 in the group k+1 mod n, and a_2 in the group k+2 mod n, each time at the same position. When n is even it gives a sequence of length n/2, but when n is odd it is twice more efficient, giving a sequence of length n.

It may be that experts in graph theory will recognize this problem. Indeed, let us draw a graph G where each vertex is a student, linking them if they have been in the same group once. We can then draw the triangle graph of G : this is the graph whose vertices are triangles in G, being adjacent if the triangles share an edge. Each time we form a new group we select a vertex in the triangle graph which is not adjacent to any vertex already chosen. However we must also select vertices in such a way as to partition our 3n students, and I do not see how this condition can be translated in the triangle graph. But maybe someone does.

I would be very interested if anyone recognizes a well-known problem, breaks it, or make progress one way or another !