Library / HongKong -23 IMO Selection Tests /1 of 10

HongKong -23 IMO Selection Tests, 2022

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Hong Kong

There are 50 rods of lengths $1, 3, 5, 7, \ldots, 99$ . How many ways are there to pick three of these rods to form a triangle?

Solution

The answer is $\binom{50}{3}$ minus the number of choices of three rods that violate the triangle inequality. The number to be subtracted is the size of the set
$S = \{(a, b, c) : 1 \le a < b < c \le 99,\ a + b < c,\ a, b, c \text{ are odd numbers}\}.$
Note that for $(a, b, c) \in S$ , $a+b$ is an even number between $4$ and $98$ (inclusive). For each such even number, we can easily count the number of such pairs $(a, b)$ , and for each such $(a, b)$ we can easily count the number of choices of $c$ for which $(a, b, c) \in S$ .

As an example, if we fix $a + b = 20$ , there would be $5$ choices for $(a, b)$ , namely, $(1, 19)$ , $(3, 17)$ , $(5, 15)$ , $(7, 13)$ and $(9, 11)$ . For each of these $5$ pairs of $(a, b)$ , there are $40$ choices of $c$ for which $(a, b, c) \in S$ , namely, $21, 23, 25, \ldots, 97, 99$ .
In the same way, we can see that for each even number $2k$ where $k \in \{2, 3, 4, \dots, 48, 49\}$ , there would be $\lfloor \frac{1}{2}k \rfloor$ choices of $(a, b)$ for which $a + b = 2k$ , and for each such $(a, b)$ there would be $50-k$ choices of $c$ for which $(a, b, c) \in S$ . This can be summarized by the following table:

Value of $k$	Value of $a + b$	No. of choices of $(a, b)$	No. of choices of $c$
2	4	$\lfloor \frac{2}{2} \rfloor = 1$	$50 - 2 = 48$
3	6	$\lfloor \frac{3}{2} \rfloor = 1$	$50 - 3 = 47$
4	8	$\lfloor \frac{4}{2} \rfloor = 2$	$50 - 4 = 46$
5	10	$\lfloor \frac{5}{2} \rfloor = 2$	$50 - 5 = 45$
...	...	...	...
48	96	$\lfloor \frac{48}{2} \rfloor = 24$	$50 - 48 = 2$
49	98	$\lfloor \frac{49}{2} \rfloor = 24$	$50 - 49 = 1$

From the table, we see that

\begin{aligned} |S| &= 1 \times 48 + 1 \times 47 + 2 \times 46 + 2 \times 45 + \dots + 24 \times 2 + 24 \times 1 \\ &= 1 \times 95 + 2 \times 91 + \dots + 24 \times 3 \\ &= \sum_{k=1}^{24} k(99 - 4k) \\ &= 99(1 + 2 + \dots + 24) - 4(1^2 + 2^2 + \dots + 24^2) \\ &= 99 \cdot \frac{24 \cdot 25}{2} - 4 \cdot \frac{24(24+1)(2 \cdot 24+1)}{6} \\ &= 10100 \end{aligned}

and so the answer is

\binom{50}{3} - 10100 = \frac{50 \cdot 49 \cdot 48}{6} - 10100 = 9500.

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.