An exam centre is going to prepare question papers for 160 students where each paper has 9 questions from 9 different topics (one question per topic). They can allow upto 2 collisions, i.e. at most 2 out of the 9 questions can be the same for any two of the papers. What is the minimum number of questions that should be prepared for each topic?
My work follows:
First I tried to find out what is total number of total questions that needs to be prepared. I was thinking of using Inclusion-Exclusion principle but then it's too big to calculate the cardinality of the union of 160 sets.
Then I started to work on small number of sets starting from 2, 3, 4, ... and progressing in the hope of finding any pattern or logic. Finally it would be like a 160 x 9 matrix where no two rows have more than 2 elements in common. I prepared the first few rows as shown below:
A1 B1 C1 D1 E1 F1 G1 H1 I1
A1 B2 C2 D2 E1 F2 G2 H2 I2
A2 B1 C2 D3 E2 F1 G2 H3 I3
A3 B3 C1 D2 E2 F3 G1 H2 I3
A B C D E F G H I
I am getting stuck at the 5th row and not able to bring 2 elements common from first 4 rows. Not able to determine if it is logically bound to happen or is there something wrong in my initial technique of optimisation.
1 Paper: Minimum number of total questions = 9
2 Papers: Minimum number of total questions = 9 + 7 = 16
3 Papers: Minimum number of total questions = 9 + 7 + 5 = 21
4 Papers: Minimum number of total questions = 9 + 7 + 5 + 3 = 24
5 Papers: Minimum no. of total questions = 9 + 7 + 5 + ? = ?
Next another thought came to my mind.
I've been thinking about the simpler case where there is at most one collision. (That is, questions may be re-used, but not in a way that two exam papers contain the same two questions.)
Suppose we only need two questions (denoted by A and B topic questions) instead of 9. With just two questions, the "one-collision" requirement is the same as saying all the papers are unique.) Then we can show that 26 questions suffices to generate 160 papers. Here's how:
First, we show there have to be at least 26 questions. This comes from the pigeonhole principle. Let k be the number of A questions. Then there is some A question that occurs at least 160/k times, and so we need at least 160/k B questions to go with this one, for a total of k + 160/k (rounded up to the next integer) questions. The minimum value of this expression is 26, which occurs for all k in the range 10 <= k <= 16.
But I am not able to generate an idea on how to proceed to solve the given problem. How to Mathematically model the problem statement? What I am not very sure about is whether we try to find out the smallest number of total questions required, say Q, for a subset of N papers and then our answer shall be Q*(floor(160/N)) + Q', where Q' is smallest number of total questions required for the remaining 160 - N*(floor (160/N)) papers.
Please, help me as I am missing the required optimisation strategy to be used.
High Regards,
Shamik Banerjee
(Not a complete solution)
Showing that we need at least 5 question in each topic.
Let there be $Q$ questions in each topic.
Set up the standard incidence matrix of 160 rows as students and $9Q$ columns as questions.
Each row has 9 1's in it, for a total of $160 \times 9 =1440$ 1's.
Let $c_i$ be the number of 1's in each column. We have $ \sum c_i = 1440.$
We bound the number of column pairs of 1's:
Every 2 rows share at most 2 column pairs, so there are $\leq 2\times{160 \choose 2} = 25440 $ column pairs.
The number of columns pairs is $ \sum { c_i \choose 2 } \geq 9Q \times {\frac{1440}{9Q} \choose 2 } $.
Solving $25440 \geq 9Q \times {\frac{1440}{9Q} \choose 2 } $ gives us $ Q \geq \frac{480}{109}$ so $ Q \geq 5$.
Trying to show $Q = 5$ works.
Showing that $Q = 13$ is more than sufficient.
Consider the $13^2=169$ pairs of integers $(i, j)$ with $1 \leq i, j \leq 13 $.
Student $S_{(i,j)} $ for topic $T $ will get question $i+tj \pmod{13}$.
Then Student $S_{(i_1, j_1)}$ and $S_{(i_2, j_2)}$ will share a common question if $ i_1 - i_2 = t (j_1 - j_2) \pmod{13}$, which has a unique solution $t$, so they will share at most 1 question in common.
$Q = 9 $ is sufficient
Claim from Rob Pratt in the comments.