Designing student workgroups for laboratory experiments

 Success

About Thomas' mathematical adventures:

I have a passion for recreational mathematical puzzles. Especially combinatorical puzzles or puzzles involving square numbers. My approach is normally some mathematical research combined with brute force CPU power. Often I am not able to solve the puzzle, but sometimes I am. However even when I fail to find a solution the information gained can be interesting since it can reveal the minimum size of a solution or revealing patterns in the numbers. This is the second adventure in my series of 'mathematical adventures', and this adventure was a success! Over the next weeks I plan to write about another 5-6 different mathematical adventures.

Abstract:

This puzzle has a arisen from a real life situation and its solution has real life applications as well! Technically it belongs to the mathematical field of Design Theory. I was given the problem from a friend of mine, a danish gymnasium teacher, who was trying to make a schedule for his students. Instead of having the same teams of the same students doing exercises together, can you design the teams so no two students are in the same group more than once? In its original form it was stated:

27 students has to perform 9 different laboratory exercises over 9 different days. The students are doing each exercise in a team(group) of 3 students. Of course each student can only do 1 exercise each day and he must do all 9 of the different exercises.
Can you make a schedule such that no pair of students never meet in more than 1 team?
(Try see the solution for the smaller problem with 12 students below, this will make it more clear what the problem is about!)

I did manage to solve this problem and in fact the same problem for many other different sizes of students,team size and number of exercises. However I am not proud it took me so long to solve it, since I have studied Design Theory. But at least several gymnasium teachers gave up before giving it to me also... After some mathematial research and reading up on Design Theory I could not find the solution. So I made a program to crack the combinations by brute force using 2+ weeks of CPU. However my program failed the problem, but was able to solve similar smaller problems. Almost one year later I had an 'eureka moment' while working on another problem and solved this problem instantly.

Laboratory

Initial thoughts and approach:

At first this problems sounds very similar to the famous Kirkman's schoolgirl problem which had a unique solution. But there is a huge difference. In the schoolgirl problem the girls are also in teams of 3. But it was not a schedule with n excercises and n days (n=9 in my problem), but instead 7 days and 5 exercises. Also in Kirkman's problem every girl(student) are in team/group with every other girl exactly once! While in my problem they are in group with every other student maximum 1 time. That is 0 or 1 time. Kirkman's problem is a more typical problem from Design Theory which has the restriction "exactly 1 (or n) times)" instead of "maximum 1 (or n) times. These "exactly"-problems are symmetric for each element (student) and it is this type of problems that has been researched the most. So I could initially not find anything usefull from Design Theory. Often you can start with one of these "exactly" solutions and expand or reduce it to a problem similar to mine, but I failed.

Back to my problem. Each team of students (1,2,3) will have 3 pairs of students meeting, namely (1,2), (1,3) and (2,3). Since there are 9*9=81 teams totally a solution will have exactly 3*81=243 unique student pairs meeting. With 27 students there are 27*26/2=351 possible pairs. So if a solution exists only 243 different pairs of students will meet compared to the total number of 351 possible pairs. So IF a solutions exists there will be many pairs of students not meeting. This gives the teacher a little more freedom when making the teams. He can decide many pairs of students to avoid having in the same group. Ie. not having two trouble makers in the same group, or two very weak students and so on. The growth complexity of this problem is unfortunately n! (factorial) where n is the number of students. This is a very brutal growth complexity and it is actually WORSE than exponential growth shocked. I started trying to solve the similar problem but for fewer students. The general description of the parameters in the problem is:
3n students, team size of 3 students, n different exercises over n different days, where n>1.

n=1: Solution exists!
This is pretty trivial:
Exercise1
Day1 (1,2,3)


n=2: Not possible!
Trying to solve it by hand makes it obvious it is not possible.

n=3: Not possible!
Trying to solve it by hand makes it obvious it is not possible.

n=4: Solution exists!
My program found the solution instantly.
Exercise1Exercise2Exercise3Exercise4
Day1(1,2,3)(4,5,6)(7,8,9)(10,11,12)
Day2 (4,9,12) (1,7,11) (3,5,10) (2,6,8)
Day3(6,7,10) (3,8,12) (2,4,11) (1,5,9)
Day4 (5,8,11) (2,9,10) (1,6,12) (3,4,7)
Notice that many pair of students does not share a team at all like (1,8) etc.

n=5: Solution exists!
My program found the solution within a few seconds.
Exercise1Exercise2Exercise3Exercise4Exercise5
Day1 (1,2,3) (4,5,6) (7,8,9) (10,11,12) (13,14,15)
Day2(9,11,15) (3,12,14) (2,4,13) (1,5,7) (6,8,10)
Day3(5,10,13) (1,8,15) (3,6,11) (4,9,14) (2,7,12)
Day4(6,7,14) (2,9,10) (5,12,15) (3,8,13) (1,4,11)
Day5(4,8,12) (7,11,13) (1,10,14) (2,6,15) (3,5,9)


n=6: Solution exists!
It can take several hours for my program to find a solution for n=6. But a n=6 solution is a very special, since this does not follow my general solution of the problem! So brute force CPU was not totally wasted. I wonder if there still is an easy way using design theory for this case.
Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6
Day1 (1,2,3) (4,5,6) (7,8,9) (10,11,12) (13,14,15) (16,17,18)
Day2(11,14,18) (3,9,15) (1,5,16) (4,8,17) (2,7,12) (6,10,13)
Day3(5,8,13) (12,14,16) (2,4,10) (3,6,18) (9,11,17) (1,7,15)
Day4(6,7,17) (1,8,11) (12,13,18) (2,15,16) (3,5,10) (4,9,14)
Day5(4,12,15) (7,10,18) (3,14,17) (1,9,13) (6,8,16) (2,5,11)
Day6(9,10,16) (2,13,17) (6,11,15) (5,7,14) (1,4,18) (3,8,12)


n=7+:No solution found
I used more than 2+ weeks CPU to try solve n=7, but no solution. I also tried for n=8 and the original problem n=9 with no luck.

1 YEAR LATER...EUREKA

In this schedule students are labeled from 0 to 26, I am too lazy to change it.
Exercise1Exercise2Exercise3Exercise4Exercise5Exercise6Exercise7Exercise8Exercise9
Day1 (0,9,18) (1,10,19) (2,11,20) (3,12,21) (4,13,22) (5,14,23) (6,15,24) (7,16,25) (8,17,26)
Day2 (1,11,21) (5,17,22) (8,15,19) (4,10,25) (6,14,20) (0,16,24) (3,9 ,26) (2,13,18) (7,12,23)
Day3 (2,12,22) (8,13,24) (6,10,23) (1,16,20) (5,11,26) (7,15,21) (0,17,25) (4,9,19) (3,14,18)
Day4 (3,13,23) (4,15,18) (1,14,25) (7,11,24) (2,17,21) (6,12,19) (8,16,22) (0,10,26) (5,9 ,20)
Day5 (4,14,24) (6,9 ,21) (5,16,18) (2,15,26) (8,12,25) (3,10,22) (7,13,20) (1,17,23) (0,11,19)
Day6 (5,15,25) (0,12,20) (7,9 ,22) (6,17,18) (3,16,19) (1,13,26) (4,11,23) (8,14,21) (2,10,24)
Day7 (6,16,26) (3,11,25) (0,13,21) (8,9 ,23) (7,10,18) (4,17,20) (2,14,19) (5,12,24) (1,15,22)
Day8 (7,17,19) (2,16,23) (4,12,26) (0,14,22) (1,9 ,24) (8,11,18) (5,10,21) (3,15,20) (6,13,25)
Day9 (8,10,20) (7,14,26) (3,17,24) (5,13,19) (0,15,23) (2,9 ,25) (1,12,18) (6,11,22) (4,16,21)


And this is how to do solve the problem:

I was working on another problem that was involving Mutually Orthogonal Latin Squares(MOLS). , which actually solved that problem also. Finding MOLS (and how many exists for a giver number) is a very hard problem, but I am just using the results for those MOLS that has been found. This link list some MOLS. I will now show how to solve the problem for the small n=4 case. The system used for higher n is the same. For n=4 there are 3 MOLS, and you need 3 or more MOLS to solve the problem. If there are more 3 you just take any 3 of them. So n=4 can be solved using MOLS. The (only) 3 MOLS for n=4 are:
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0 		0 1 2 3
2 3 0 1
3 2 1 0
1 0 3 2 		0 1 2 3
3 2 1 0
1 0 3 2
2 3 0 1

At first these 3 MOLS all have numbers from 0 to 3. But for my problem you should see the 3 MOLS as each having 4 different elements. I add 4 too each number in MOLS number 2 and add 8 to each number in MOLS number 3. Giving:
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0 		4 5 6 7
6 7 4 5
7 6 5 4
5 4 7 6 		8 9 10 11
11 10 9 8
9 8 11 10
10 11 8 9

The next step is to 'overlay' all 3 MOLS from above on top of each other and make the triples of the 3 students in the same cell.
Exercise1Exercise2Exercise3Exercise4
Day1(0,4,8) (1,5,9) (2,6,10) (3,7,11)
Day2 (1,6,11)(0,7,10) (3,4,9) (2,5,8)
Day3(2,7,9) (3,6,8) (0,5,11) (1,4,10)
Day4 (3,5,10) (2,4,11) (1,7,9) (0,6,9)

And you are done...

The construction makes it clear what pairs of students that are never meeting, it is those that belong to the same MOLS. So the students 0,1,2,3 are never in a team/group together. Same goes for 4,5,6,7 and 8,9,10,11. On the other hand will students from different MOLS always meet excactly once. And this makes it easy to make balanced groups for the teacher. Put the 1/3 worst students in MOLS#1, the middle 1/3 in MOLS#2 and the best 1/3 in MOLS#3.

Here is a list of how many MOLS of order n that exists for the first 20 values of n (all are exact values):
n 234567891011121314151617181920
Number of MOLS of order n123416782105123415163184


For n=6 and n=10 it can be seen there are not 3 or more MOLS. So my method does not work for these. But I still solved the n=6 problem by brute force CPU, so maybe there is a solution for n=10 as well. The solution can just not be constructed from 3 MOLS of order 10 since it is known there only are 2. So CPU power did contribute with something new, but it was pure math that solved this problem. 3 MOLS was needed because of the team/group size of 3. And if there are 4 MOLS (n=5 or n=15 etc.) you can solve the similar problem with team/group size =4 instead of 3.

The common design problem is typical a situation where every has to meet every exactly once. This arises in sports tournaments etc. This link(Social Golfer problem) has gathered some of the most usefull designs. These designs are generally hard to find since they are often only only published in the mathematic article where they were found etc.

Algorithm:

WLOG the schedule for the first day can be (1,2,3) (4,5,6) .... and so on. So completing day1 was easy. I then completed one more day at a time, if possible. It was never a problem with the first 3 days, after that it got harder. There are too many combinations to even try start from an end, I had much more luck by picking the triplets random (and checking each student had not allready done that excercise etc.) The further I got up in days completed, the more I time I gave the algorithm to try complete the day. After enough time, instead of giving up and starting all over, I rolled-back 1 day and tried again. This slowly improving the number of completed days and exercises that day. After enough time and still not getting any further, the program started all over again. No real system. Just trying random and checking conditions combined with making small changes back-wards and going forwards again to see if that improved anything.

Contact information:

If you have any questions or contributions to the problem you can contact me at thomas.egense@gmail.com