Maths Olympiad Prep

Library / /1 of 11

, 2022

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

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

Solution

The answer is (503)\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):1a<b<c99, a+b<c, a,b,c are odd numbers}. 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)S(a, b, c) \in S, a+ba+b is an even number between 44 and 9898 (inclusive). For each such even number, we can easily count the number of such pairs (a,b)(a, b), and for each such (a,b)(a, b) we can easily count the number of choices of cc for which (a,b,c)S(a, b, c) \in S.

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

Value of kkValue of a+ba + bNo. of choices of (a,b)(a, b)No. of choices of cc
2422=1\lfloor \frac{2}{2} \rfloor = 1502=4850 - 2 = 48
3632=1\lfloor \frac{3}{2} \rfloor = 1503=4750 - 3 = 47
4842=2\lfloor \frac{4}{2} \rfloor = 2504=4650 - 4 = 46
51052=2\lfloor \frac{5}{2} \rfloor = 2505=4550 - 5 = 45
............
4896482=24\lfloor \frac{48}{2} \rfloor = 245048=250 - 48 = 2
4998492=24\lfloor \frac{49}{2} \rfloor = 245049=150 - 49 = 1

From the table, we see that
S=1×48+1×47+2×46+2×45++24×2+24×1=1×95+2×91++24×3=k=124k(994k)=99(1+2++24)4(12+22++242)=9924252424(24+1)(224+1)6=10100 \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
(503)10100=504948610100=9500. \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,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.