Probability involving unique group combinations

If I have $30$ objects and $5$ buckets that each hold $6$ objects, how many times could I put the objects into the buckets without an object being in the bucket with an object it has previously been grouped with? So, for each round you would empty all of the objects from the buckets and place them into buckets again (they could be in the same bucket multiple times, just not see another object multiple times).

Edit: A better example would be $120$ objects in $20$ buckets that hold $6$ objects. No object can ever be in a bucket with another object that it has seen previously.

-

migrated from stackoverflow.comMay 14 '12 at 18:05

This question came from our site for professional and enthusiast programmers.

It's not at all clear what is being asked here. Please try to explain better. – ypercubeᵀᴹ May 12 '12 at 22:07

I think the answer may be zero one. Distribute each object (integers 1-30) into 5 buckets in order:

B1 B2 B3 B4 B5
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


Rotate the horizontal lines to redistribute across each bucket

 1  2  3  4  5 // this line stays constant
10  6  7  8  9 // objects shifted to the right once
14 15 11 12 13 // twice
18 19 20 16 17 // three times
22 23 24 25 21 // four times


Everything is fine up to this point. But now, where can we put 26, given that it can't live with 1, 6, 11, 16, or 21, which have all been distributed across the five buckets? Nowhere. Same holds true for 27, 28, 29, and 30.

Maybe there's a more interesting answer if you had 6 buckets of 5 elements.

-
You're right. I apologize, but I think I gave a bad example. It would probably be better if I had something like 90 objects with 15 buckets and 6 objects per bucket. I'm trying to figure out if there is a good formula to use for that. – Mike S May 13 '12 at 2:26

In the 30-object, 5-bucket case, as veefu points out, only one round is possible, since the six objects in bucket 1 have to go into 6 different buckets in round 2, but there aren't 6 buckets for them to go into.

90 objects with 15 buckets, object number 1 must be with 5 new objects every round, there are 89 objects other than object 1, so at most 17 rounds are possible ($17\times5\le89\lt18\times5$). Whether 17 rounds are actually possible is another (and generally much harder) question. Similarly, with 120 objects in 20 buckets, you certainly can't have more than 23 rounds, but it's hard to say whether 23 rounds are possible.

Fortunately, a lot of people have put a lot of work into solving this sort of question, and there are tabulations available in journals and on websites. Whether they go all the way up to 120 objects in 20 buckets, I wouldn't know. Perhaps a good search term would be "combinatorial designs".

EDIT: Another search term that might turn up something is "social golfer problem". This concerns a number of people who want to play as many rounds of golf as possible, going out in groups of 4, no two players being in the same group of four for more than one round.

-