Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Does a 10-element set have 30 3-element subsets such that each pair is in two of these 30 subsets?

share|improve this question
2  
Dear David. I fear that some will tend to think that your question is a homework, and will therefore vote to close it. To avoid that, you should indicate a little bit the context in which your questions arose. In particular, where to the numbers 10 and 30 come from? –  André Henriques Jun 18 '12 at 20:28
    
I light of Douglas Zare's answer, this question did not deserve to be closed. I vote to reopen. –  André Henriques Jun 18 '12 at 21:51
    
I still think the question would benefit from some explanation as to the OP's motivation. It isn't the kind of question that pops into my head at random, although I don't claim to be representative. –  Yemon Choi Jun 19 '12 at 0:17
2  
This question was motivated by communications scheduling. It concerns a n-node network in which up to m nodes can broadcast at a time; nodes can not receive while sending, but when not sending they can simultaneously receive from all m senders. The goal is to serve all source-destination pairs equally. n=10 and m=3 are arbitrary choices. 30 is the minimum possible because there are n(n - 1) = 90 pairs, n(n - m) = 21 can be served at a time, and lcm(90, 21)/21 = 30. I was assuming the 30 subsets are distinct, but now I see that my application doesn't need that. –  David Wasserman Jun 19 '12 at 16:48

2 Answers 2

up vote 12 down vote accepted

This asks for a $(10,3,2)$ balanced incomplete block design. These are known. There are $960$ different designs with those parameters up to isomorphism according to the CRC Handbook of Combinatorial Designs.

share|improve this answer
    
In 394 of these, the designs are simple, which means the triples are distinct. A more natural interpretation of the question would be to add the condition that the block design is simple. –  Douglas Zare Jun 18 '12 at 21:44
    
If the poster cares to chew up computer cycles, here is one approach: find 10 vectors of length 30, each with entries either 0 or 1, such that each vector has exactly 9 occurrences of 1 and such that any two distinct vectors share exactly two coordinates with ones. A little reasoning allows you to assume the form of the first three vectors (possibly four) and the computer can check for the constraints on the remaining vectors. Gerhard "Ask Me About System Design" Paseman, 2012.06.18 –  Gerhard Paseman Jun 18 '12 at 22:27

If you prefer websites to books, you can go to http://designtheory.org/database/t-designs/ and scroll down to the line that starts 2 10 30 9 3 2, and click on "download" to receive the 960 designs.

share|improve this answer
    
I actually did that first, but after installing and using bunzip I got an xml file in a format I didn't know, and I see documents describing the xml format used, but not a program which will turn it into a humanly readable form. Maybe I overlooked one. –  Douglas Zare Jun 19 '12 at 9:24

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.