Maths Olympiad Prep

Library / National Math Olympiad in Slovenia /37 of 41

National Math Olympiad in Slovenia

Combinatorics Difficulty 6.7 National Olympiad Prove it Slovenia

One day nn students participated at a sporting competition with several different disciplines. Exactly kk students competed in each of the disciplines where 3≤k≤n3 \le k \le n. Each pair of students had exactly three disciplines in common and each triple has competed in exactly two common disciplines. Determine all possible values of nn and kk.

Solution

The number of pairs of students over all disciplines can be counted in two ways. On the one hand the number of pairs is equal to the product of the number of all pairs and the number of times every pair of students competes together, which is (n2)⋅3\binom{n}{2} \cdot 3. On the other hand it must be equal to the product of the number of pairs competing in each discipline and the number of disciplines, which is (k2)⋅m\binom{k}{2} \cdot m. So,
3n(n−1)=mk(k−1).(11) 3n(n-1) = mk(k-1). \qquad (11)
Similarly, we can count the number of triples in two ways. On the one hand it is equal to (n3)⋅2\binom{n}{3} \cdot 2, on the other hand it must be (k3)⋅m\binom{k}{3} \cdot m. So,
2n(n−1)(n−2)=mk(k−1)(k−2). 2n(n-1)(n-2) = mk(k-1)(k-2).
Since k,n≥3k, n \ge 3, we can divide one equation by the other and get
2(n−2)3=k−2. \frac{2(n-2)}{3} = k-2.
This implies that n−2n-2 is divisible by 3 so we can write n=3l+2n = 3l + 2, where l∈Nl \in \mathbb{N}. Inserting this back into the equation we get k=2l+2k = 2l + 2. We can then use (11) to get
m=3n(n−1)k(k−1)=3(3l+2)(3l+1)(2l+2)(2l+1). m = \frac{3n(n-1)}{k(k-1)} = \frac{3(3l+2)(3l+1)}{(2l+2)(2l+1)}.
However, D(3l+1,2l+1)=D(2l+1,l)=1D(3l+1, 2l+1) = D(2l+1, l) = 1 and D(3l+2,2l+1)=D(2l+1,l+1)=D(l+1,l)=1D(3l+2, 2l+1) = D(2l+1, l+1) = D(l+1, l) = 1. So, 2l+12l+1 and (3l+2)(3l+1)(3l+2)(3l+1) are relatively prime and 2l+12l+1 divides 3. This is only possible when l=1l=1 and consequently n=5n=5, k=4k=4 and m=5m=5.
Finally, we must check that the required arrangement of students is indeed possible for n=5n=5 and k=4k=4. Denote the students by A1,A2,…,A5A_1, A_2, \dots, A_5. Here is one possible arrangement that satisfies the conditions given in the problem:
{A1,A2,A3,A4},{A1,A2,A3,A5},{A1,A2,A4,A5},{A1,A3,A4,A5},{A2,A3,A4,A5}.\{A_1, A_2, A_3, A_4\}, \{A_1, A_2, A_3, A_5\}, \{A_1, A_2, A_4, A_5\}, \{A_1, A_3, A_4, A_5\}, \{A_2, A_3, A_4, A_5\}.
Thus, the only solution is n=5,k=4n=5, k=4.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.