Today at my virtual talk at the Scholar Search Education Forum at Northwestern, a student asked me about the hardest math problem I’ve solved. I thought of the hardest problem I haven’t solved. I love it because it came from a real situation!
Say there are 36 people at a workshop. They get in groups of 6 and work for a while. Then, they regroup into new groups, so no one is in a group with anyone they’ve been with before. How many times can they regroup before someone has to be in a group with someone they’ve worked with before?
I also wonder, how could you extend this problem? If you’ve answered the specific problem, what else does it make you wonder?
They can do this three times. Arrange the people in a six-by-six array, and group the people by rows, by columns, and by diagonals. The diagonal grouping is shown below.
Group 1: 11, 22, 33, 44, 55, 66
Group 2: 12, 23, 34, 45, 56, 61
Group 3: 13, 24, 35, 46, 51, 62
Group 4: 14, 25, 36, 41, 52, 63
Group 5: 15, 26, 31, 42, 53, 64
Group 6: 16, 21, 32, 43, 54, 61
It is not possible to separate them into groups more than three times. The reason is that we can assume that the first grouping is by rows, and the second grouping is by columns, after rearranging the people if necessary. If this is the case, then any future regrouping will be represented by a latin square. For example, the diagonal grouping is represented by the following latin square.
1 2 3 4 5 6
6 1 2 3 4 5
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
2 3 4 5 6 1
If we could group the people four times, then we would obtain two orthogonal latin squares, but it is well-known that orthogonal latin squares of order six do not exist.
Hi Dave,
I love this problem because it’s accessible on many levels, at least to start trying to organize and make sense of the data. I’ve had some students try this with pencil and paper and they reported more than 4 groups (7 or more!) I’m curious to see if you and they had different interpretations of the problem, or if there was some overlap in their groups they didn’t notice? Or if there are actually some other ways to find groups out of this 6 by 6 array that you didn’t notice?
I’m also curious why the diagonal grouping works. And why you can’t find other groupings in the 6 x 6 array that work and don’t form an orthogonal latin square.
And, what if we did groups of size 4? Would there still only be 3 ways? What if there were 60 people in room instead of 36?
Thanks for commenting!
Max
This problem feels like the kind where I try to solve a simpler problem first and see if I can iterate in difficulty until I get to the harder problem.
So I thought maybe 12 people in groups of six would be an easier problem that would teach me something about the harder problem. So here are my two groups.
1 2 3 4 5 6 7 8 9 10 11 12 So I’m going to do a little re-arranging.
Pick two people that weren’t together before and start a new group. Let’s pick 1 and 7. Four more people have to go into this group, and there’s no one else who hasn’t been with 1 or 7. So I say there is only one arrangement of 12 people in groups of six. Agree?
Now I’m going to try 18 people in groups of six.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Now let’s start a new group again. Let’s pick 1, 7, and 13. Three more people have to go into the group, and there’s no one else who hasn’t been with 1, 7, or 13. So I think there’s only one arrangement of 18 people in groups of six. Agree, or am I missing something here?
Now 24 people.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Start a new group with 1, 7, 13, 19, so once again, I can’t make a second group.
So I finally see that IF there’s going to be a different arrangement, there’s going to need to be at least 36 people.
So 36 people
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
Now I’m going to take my former strategy and make a new group of the first person in each group
1 7 13 19 25 31
2 8 14 20 26 32
3 9 15 21 27 33
4 10 16 22 28 34
5 11 17 23 29 35
6 12 18 24 30 36.
etc. Gotta quit now, but will return. Feel free anyone to comment.
Oh, that’s neato. I never thought to keep the breakout-group sizes the same and change how many people are in the big group! I thought of doing different square numbers of people in the big group, like 1 person in groups of 1, 4 people in groups of 2, 9 people in groups of 3, etc.
I definitely ended up arranging people the array or matrix style you used above. I wonder how else we could represent the groups?
Max
Hi,
I have spent the last 10 years designing tools to help people with problems like these. Through my research I have never found anyone who has ever labelled this type of process (organising people into different groups so that they are never in the same group twice). Hence I decided that “Orthogonal Regrouping” is an appropriate label and have started promoting this term in the last year. Orthogonal regrouping is well known in relation to the Kirkman’s schoolgirl problem and the social golfer problem. It has potential in group assessments in educational assessment (reducing bias in group assessment by broading the range of people work with), business networking (maximising the speed networkers meet new people) and industry skills development (broadening experience of members of a large team by broadening the range of people they work with) as well as many other opportunities. While orthogonal regrouping has been an exercise that people have been trying to master for more than 100 years, there is still a progress that people need to improve on it for it’s potential to be realised.
Can anyone suggest an algorithm for finding solutions to a similar problem, but with a larger number of people, say 160, divided into 20 groups of 8? The theoretical maximum number of groupings would be 22; is that achievable? If not, what is? Thanks!
Hi Jim,
I can organise 160 people into groups of 7 for 23 groupings (I call them rounds). It is possible to get all 160 people meeting everyone if there are 6 more groupings but the groups are only 4-5 people. Otherwise in groups of 7 everyone gets to meet 138-139 people. It takes a bit of work to set up. That’s the closest I can do to your request.