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 was working out some combinations for a game, when I hit upon a problem that seems unsolvable. I'm wondering if some existing mathematics (probably in graph theory or combinatorics) covers this particular class of problem. To express it without any game-specific terminology:

I have a set of 6 numbers {1,2,3,4,5,6} from which I will create 3 number combinations. These combinations are always ordered and never contain duplicates, such as {123,134,145,156...}. Simple combinations tells me there are 20 such configurations.

Now from those configurations, I wish to select sets of 4 each, such that no two numbers recur in any of the 4 triplets. An example would be {123,145,246,235}.

My goal was to sort all 20 combinations into 5 sets of 4, but I don't think it's possible. I always end up with 2 pairs that repeat, either in 2 separate sets or both in one set, like {123,145,236,245} (23 and 45 occur twice). Note that being split still counts, so {234,245} is still a failure because 24 repeats.

I figure this problem must be analogous to a node walking problem or something like that, but I don't know the math well enough to prove that no solution exists or to find similar problems by searching.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

This sounds a lot like block design.

This has actually found some very practical uses!

share|improve this answer
    
Excellent! That seems like exactly what I was talking about. Thank you. –  CodexArcanum Aug 17 '12 at 16:33

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.