4
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

This sounds a lot like block design.

This has actually found some very practical uses!

$\endgroup$
1
  • $\begingroup$ Excellent! That seems like exactly what I was talking about. Thank you. $\endgroup$ Aug 17, 2012 at 16:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .