Does a 10-element set have 30 3-element subsets such that each pair is in two of these 30 subsets?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ 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? $\endgroup$– André HenriquesJun 18, 2012 at 20:28
-
$\begingroup$ I light of Douglas Zare's answer, this question did not deserve to be closed. I vote to reopen. $\endgroup$– André HenriquesJun 18, 2012 at 21:51
-
$\begingroup$ 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. $\endgroup$– Yemon ChoiJun 19, 2012 at 0:17
-
2$\begingroup$ 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. $\endgroup$– David WassermanJun 19, 2012 at 16:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Jun 18, 2012 at 21:24
-
$\begingroup$ 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. $\endgroup$ Jun 18, 2012 at 21:44
-
$\begingroup$ 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 $\endgroup$ Jun 18, 2012 at 22:27
$\begingroup$
$\endgroup$
1
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.
answered Jun 19, 2012 at 1:46
-
$\begingroup$ 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. $\endgroup$ Jun 19, 2012 at 9:24