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

I’m reading my post from three years ago, and I am finding it somewhat difficult to understand, so I will try again.

Suppose that we divide the class into groups of 6, and then we regroup them into groups of 6, so nobody is in a group with anyone that they’ve been with before. Then each participant can be identified with an ordered pair (x, y), where x is the number of the first group and y is the number of the second group.

Now we group the students a third time, and we make a 6 by 6 table. We write z in position (x, y) if the participant labeled (x, y) is assigned to group z. The condition that no student is grouped with anyone they’ve been with before implies that the 6 by 6 table is a Latin square.

If we could group the students a fourth time, we would get another Latin square which is orthogonal to the first Latin square. But it is known that orthogonal 6×6 Lain squares do not exist.

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.

My brother teaches conversational English class in Korea where cultural norms inhibit people from speaking to strangers unless in a structured situation which calls for them to do so, and he’s asked me for help in what you term orthogonal grouping so everyone meets everyone else during the first day or two of the term. Class sizes are 20 to 28 students with optimum group size being 4 (2nd choice is 3; 5 is a last resort). I’m struggling to come up with a good solution. I’ve based most of my tries on 25 people, and it seems I need 8 rounds but everything I’ve tried ends up with at least two people being in the same group by the 4th or 5th round.

I’d appreciate a reply if you can help. Thanks.

Hi Kathy.

The first question above (7 rounds of 6 groups of 6) is impossible.

Your question about splitting up 25 people into groups of 4 can be done over 9 rounds from memory. I will try to find it for you. As a teacher, my advice is that making everyone go with everyone else may not be necessary. If you can ensure that every child gets to interact with at least 60% of the rest of the class, that is still a very powerful way of ensuring an interactive culture in your class. My belief is the key benefit of orthogonal Regrouping are bully prevention and the potential development of KPIs that bias is minimised for group assessment.

Hi Kathy,

I just wrote a web app to solve this problem. It doesn’t give an optimal solution, but it’s a good start. http://gotmath.com/splitup/

Hi Kathy,

Here is the arrangement for 25-28 students in groups of 4 so that they meet everyone in 9 rounds on my Google Drive Page:

https://docs.google.com/spreadsheets/d/1mimFwt7qjuF29J7mpFBcA6Q-2nn0vB9Ckq15UPzM_A8/edit?usp=sharing

Kathy, If you can find postage fees, I can potentially supply cards that I have developed for free for testing. Each set cost me $20AU to make but I don’t try to make money with them any more as I have enough work with my day job.