Combinatorics – Splitting 100 People into 25 Groups of 4 Without Repeating Groups

combinatorics

I have a counting problem for work that we've been trying to solve for a bit now, and have finally come here for help. Here is the problem:

Given 100 people, split the 100 people into groups of 4. Now we have 25 groups of 4 people. The question is, how many times can the 100 people be split into 25 groups of 4 so that no one is in a group with the same person twice?

Ideally, we are looking for a general solution to the problem. We have worked out a couple of smaller versions by hand. For instance, for 16 people split into groups of 4, the groups can be made 3 three times.

Any ideas?

Best Answer

This is the Social Golfer Problem. You're looking for Resolvable Steiner Quadruple Systems. The highest known solution I know about is for 32 golfers playing in foursomes for 10 days.

The names of what actually needs to be looked for are somewhat scattered. For example, 36 golfers in foursomes can play for 11 days. This is a 4-RGDD of type $2^{18}$.

Theoretically, the 100 golfers in your group could be split into foursomes 33 (1 person + 3x33) times, but that would be a perfect covering, and those are pretty well known. This isn't a perfect covering listed in the Handbook of Combinatorial Designs, so it's likely something tricky, or nonperfect and trickier.

The La Jolla Covering Repository stops at 99 points. There is a C(99,4,2) = 817 design... if this was resolvable (splittable into groups covering 1-100), 817/25 = 32.65, so maybe you could get 32 splits.

Maybe the Design of the Century is resolvable. In that case, you've got a perfect solution. That paper has various references for this particular design. In any case, you'll find an answer within combinatorial methods far faster than with any kind of brute force approach.

Related Question