3
$\begingroup$

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.

2 Answers 2

1

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.

0

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