Maths Olympiad Prep

Library / /66 of 82

Combinatorics Difficulty 6.3 National olympiad Prove it Croatia

A group of twenty children has 100100 ribbons. Each ribbon is being held at its ends by two children. Two children may hold together at most one ribbon. Let us assume that a pair of ribbons such that its four ends hold different children can be chosen in 40504050 ways. Prove that each child holds the same number of ribbons. (Iran 2003)

Solution

We enumerate the children by numbers 1,2,,201, 2, \dots, 20. Let us denote by did_i the number of ribbons that are being held by the child with number ii. Since each ribbon is being held by two children we have that
i=120di=2100=200. \sum_{i=1}^{20} d_i = 2 \cdot 100 = 200.
The number of all pairs of ribbons is 100992=4950\frac{100 \cdot 99}{2} = 4950.
A pair of ribbons such that its four ends are not being held by different children is given by a pair of ribbons such that there is a child who holds one end of each of the two ribbons in that pair.
Hence
i=120di(di1)2=49504050=900. \sum_{i=1}^{20} \frac{d_i \cdot (d_i - 1)}{2} = 4950 - 4050 = 900.
From here it follows that
i=120di2=1800+i=120di=1800+200=2000. \sum_{i=1}^{20} d_i^2 = 1800 + \sum_{i=1}^{20} d_i = 1800 + 200 = 2000.
By the AM–QM inequality we have
10=d1+d2++d2020d12+d22++d20220=10. 10 = \frac{d_1 + d_2 + \dots + d_{20}}{20} \le \sqrt{\frac{d_1^2 + d_2^2 + \dots + d_{20}^2}{20}} = 10.
Since the equality in AM–QM inequality is obtained if and only if all did_i are equal, the claim follows.

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 and solution reproduced as published; topic and difficulty added by this site.