The exam has $25$ topics, each of which has $8$ questions. On a test, there are $4$ questions of different topics. Is it possible to make $50$ tests so that each question was asked exactly once, and for any two topics there is a test where are questions of both topics?
Problem
Source: Saint Petersburg MO 2020 Grade 10 Problem 7
Tags: combinatorics
12.10.2020 00:21
Since $1+3\cdot8=25$, then we can label the topics $0$ and then a combination of the numbers $1$ through $8$ with a letter from $A$ to $C$. We will call these subtopics. Assume WLOG that the tests containing topic $0$ are $(0,1A,1B,1C)$ through $(0, 8A, 8B, 8C)$ Now there are $50-8=42$ tests remaining. Notice that two subtopics with the same number (topic) cannot appear on the remainder of these tests because they already did before Notice that the problem essentially reduces down to the same problem but with $8$ topics and $14$ tests with $4$ questions from different topics, with each pair of topics having exactly $3$ tests they both appear in. This is because once we can find an example of this, then when we expand it to $42$ tests, each pair of topics will have exactly $9$ tests they both appear in, which happens to be exactly the same number of combination of subtopics two topics can have $(3\cdot3)$, so we can assign each test two topics have in common to a unique combination of subtopics To do this, for the first two tests, assign then as topics $(1,2,3,4)$ and $(5,6,7,8)$. For the other $12$ tests, assign two tests for each possible combination of $\binom42=6$ pairs of two topics out of the first four topics. If the topics are $a,b$, then assign the first test to have topics $a+4, b+4$ and assign the other test to be the opposite. For example, the tests with topics $(1,4)$ would be $(1,4,5,8)$ and $(1,4,6,7)$ This works because if topics $x$ and $y$ are both in the range from $1-4$ or $5-8$, then we set up the tests so that there are exactly two in the first $12$ that contain both $x$ and $y$, and the one of the last two tests does as well, which gives us a total of three. If one of them is in the range from $1-4$ and other is in the range from $5-8$, then the first two tests do not contain both $x$ and $y$. But by symmetry there are $6$ tests in the first $12$ that have topic $x$. We also set it up so that exactly half of them have topic $y$, as the other set of topics comes in pairs with complement each other. This gives us a total of three tests they have in common Therefore, this construction works and we are done $\blacksquare$