Maths Olympiad Prep

Library / /3 of 9

Combinatorics Difficulty 5.9 AIME, harder Prove it Japan

Find the value of
17Ca17Cb17Cc, \sum 17C_a \cdot 17C_b \cdot 17C_c,
where the sum is taken over all triples (a,b,c)(a, b, c) of non-negative integers satisfying a+b+c=5a+b+c=5.

Solution

2349060 \boxed{2349060}
Consider a particle moving on the xyxy-plane according to the following rule: if the particle is at the point (n,m)(n, m) where nn and mm are integers, it moves in one step either to the point (n+1,m)(n+1, m) or to the point (n,m+1)(n, m+1). Consider the set Ω\Omega of all paths that a particle can take to start at the origin (0,0)(0, 0) and take steps, following the rule as above to reach the point (46,5)(46, 5). It is easy to see that there are exactly 51C551C_5 such paths. Among these paths, there are exactly 17C817C817C817C_8 \cdot 17C_8 \cdot 17C_8 (where a+b+c=5a+b+c=5) paths which cross the lines x+y=17x+y=17 and x+y=34x+y=34 at the points (17a,a)(17-a, a) and (34ab,a+b)(34-a-b, a+b), respectively. Since all the paths belonging to the set Ω\Omega cross these two lines at these points for some choice of aa and bb with 0a,b,0 \le a, b,

and a+b5a+b \le 5, we see that the value of the sum we seek is exactly the same as the number of paths belonging to the set Ω\Omega, which is 51C5=234906051C_5 = 2349060.

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.