Maths Olympiad Prep

Library / /40 of 44

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 3kn3 \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(n1)=mk(k1).(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(n1)(n2)=mk(k1)(k2). 2n(n-1)(n-2) = mk(k-1)(k-2).
Since k,n3k, n \ge 3, we can divide one equation by the other and get
2(n2)3=k2. \frac{2(n-2)}{3} = k-2.
This implies that n2n-2 is divisible by 3 so we can write n=3l+2n = 3l + 2, where lNl \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(n1)k(k1)=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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