How many problems are needed on a list so that no two students have more than 1 in common when they each choose 3? 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.
 A: 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.
A: 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
