## Task A-3.5.

In a competition, $n$ students participated, and each student solved exactly three problems. For any two students, there is exactly one problem that both of them solved, and each problem was solved by exactly $k$ students. For which values of the natural numbers $n$ and $k$ is this possible?
## Solution.

For $k=1$, only one student solved a particular problem. This means there is no other student due to the condition that any two students solved one common problem.

Now let $k \geqslant 2$.

Let $A$ be one of the students. He solved exactly three problems, and each of these three problems was solved by another $k-1$ students. However, these $3(k-1)$ students are all different because no two students solved the same two problems.

On the other hand, apart from student $A$ and these $3(k-1)$ students, there are no others, as every student solved one of the problems that $A$ solved. Therefore, the number of students $n=3(k-1)+1=3k-2$.

Now consider the total number of problems. Each student solved three problems, but each problem was solved by $k$ students. Thus, the number of problems is $\frac{3n}{k}$, and this must be a natural number.

Using the formula for $n$ above, we get

$$
\frac{3n}{k} = \frac{3 \cdot (3k-2)}{k} = 9 - \frac{6}{k}
$$

from which it follows that $k$ divides 6, i.e., $k \in \{2, 3, 6\}$ (since $k \geqslant 2$).

For $k=2$, we have $n=4$ students $(A, B, C, D)$ and a total of $\frac{3n}{k}=6$ problems $(1, 2, 3, 4, 5, 6)$.

$$
\begin{aligned}
& A: 1, 2, 3 \\
& B: 1, 4, 5 \\
& C: 2, 4, 6 \\
& D: 3, 5, 6
\end{aligned}
$$

For $k=3$, we have $n=7$ students and a total of $\frac{3n}{k}=7$ problems. The desired arrangement is:

$$
\begin{aligned}
& A: 1, 2, 3 \\
& B: 1, 4, 5 \\
& C: 1, 6, 7 \\
& D: 2, 4, 6 \\
& E: 2, 5, 7 \\
& F: 3, 4, 7 \\
& G: 3, 5, 6
\end{aligned}
$$

For $k=6$, we would have $n=16$ students and $\frac{3n}{k}=8$ problems. The total number of pairs of problems is $\binom{8}{2}=28$. However, the number of pairs of problems solved by the same student is $3 \cdot 16 = 48$, since no two students solved the same two problems. Since $48 > 28$, this case is impossible. Therefore, the described situation is possible for $(n, k) \in \{(1, 1), (4, 2), (7, 3)\}$.

## NATIONAL MATHEMATICS COMPETITION

## 4th grade - high school - A variant

Dubrovnik, April 3, 2013.