Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
do you agree that 50 groups of 2 is the same as permutations without a fixed point ? Line up the first 50 people. Match them with the second. Call that arrangement of the second 1,...,50. Now you want to permute the first so that 1 is never in the 1's place etc. I think that with more groups you may have latin rectanges. I have seen asymptototics for same (C. Stein) but never the exact version. –  mike Apr 24 '12 at 18:51

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.