Given a set with $n$ items, find $x$ subsets, each one of them of size $y$, such that every two subsets share exactly one item.

I've tried to solve it with a reduction to a graph, but I got lost...


  • 3
    $\begingroup$ Can you explain why this is a computer science question? This looks to me like a question of pure math (combinatorial design etc.). Is there a reason this needs a computer science perspective or can best be answered by computer scientists? $\endgroup$ – D.W. Aug 28 '15 at 20:55
  • $\begingroup$ Sounds mostly like a block design, yeah: a (n,x,1) 2-design will give satisfy most of your conditions: (1) set of n items, (2) x subsets, (3) each pair has one in common. The downside is you can't specify y, and you instead get that each pair of items determines one subset uniquely. So this isn't /quite/ what you need. $\endgroup$ – Alex Meiburg Aug 28 '15 at 21:27
  • $\begingroup$ From a computer science perspective, you are given natural numbers x and y, and you try to minimize n. Can you come up with nice upper and lower bounds for n? Is there an algorithm to determine the minimal n and a solution achieving that minimal n? $\endgroup$ – Thomas Klimpel Aug 29 '15 at 11:00
  • $\begingroup$ I am a little bit surprised that this problem got 4 votes to be closed. It is not a problem about graphs (as originally suggested) but about combinatorics (I actually edited the text and the tag trying to make it a little bit more formal). I do believe it is a computer science question. $\endgroup$ – Carlos Linares López Aug 30 '15 at 13:28
  • $\begingroup$ I agree with @CarlosLinaresLópez . Thanks for editing my question. it seems clearer now. $\endgroup$ – user37991 Aug 31 '15 at 8:43

Browse other questions tagged or ask your own question.