I want to make a list of $p$ problems for my class of 24 students. Each student will choose 3 problems from the list with the stipulation that two different students will have at most one problem in common. How large does $n$ need to be?

And of course the obvious generalization: $p$ problems, $s \geq 2$ students and each student choosing $q\geq 2$ problems so that they never have more than $m$ problems in common where $m < q$.

Any insight in how to think about this problem is appreciated. I tried some small cases for 4,5, and 6 students, but have trouble seeing a pattern or if my solutions are minimal.


Yes it can. This particular case amounts to finding a decomposition of $K_8-I$ (where $I$ denotes a one-factor) into triangles (i.e. $K_3$ subgraphs). Here each vertex represents a question, and each triangle represents a student (the vertices of the triangle are the questions answered by that student).

For the $m=1$ and $q=3$ case (as above, but with general $s$), the best possible can be derived from Alspach's Conjecture (which has recently been proved).

Alspach's Conjecture: Given positive integers $n$ and $m_1,m_2,\ldots,m_t$, then there exists a decomposition of either $K_n$ (if $n$ is odd) or $K_n-I$ (if $n$ is even) into cycles of length $m_1,m_2,\ldots,m_t$ if and only if

  • $\sum_{i=1}^t m_i = {n \choose 2}$ if $n$ is odd,
  • $\sum_{i=1}^t m_i = {n \choose 2}-\frac{n}{2}$ if $n$ is even, and
  • $3 \leq m_i \leq n$ for all $1 \leq i \leq t$.

So, the least $n$ for which $K_n$ contains $s$ triangles will be $$\mathrm{min}\left( \left\{\text{odd } n:{n \choose 2}-sn \geq 3\right\} \bigcup \left\{\text{even } n:{n \choose 2}-\frac{n}{2}-sn \geq 3\right\} \right).$$

For general parameters, some particularly efficient cases are uniform block designs, such as Steiner systems. There's a lot of literature (and conferences) on the topic, so you're not going to get a complete answer unless you restrict the parameters in some way.


To make it possible to choose only 1 in common per two students you need

3p for 1s - 1st choice{1,2,3}

5p for 2s - 2nd choice{1,4,5}

6p for 3s - 3rd choise{2,4,6}

6p for 4s - 4th choice{3,5,6}

after this, the problem repeats. since 4s is a divider of 24s, you need 6*6=36 problems.

Cheers Fab


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.