Maths Olympiad Prep

Library / /32 of 71

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:
Let SS denote the set of all triples (i,j,k)(i, j, k) of positive integers where i+j+k=17i + j + k = 17. Compute
(i,j,k)Sijk. \sum_{(i, j, k) \in S} i j k.

Solution

Solution:
Answer: 11628=(195)11628 = \binom{19}{5}. We view choosing five objects from a row of 1919 objects in an unusual way. First, remove two of the chosen objects, the second and fourth, which are not adjacent nor at either end, forming three nonempty groups of consecutive objects. We then have i,ji, j, and kk choices for the first, third, and fifth objects. Because this is a reversible process taking a triple (i,j,k)(i, j, k) to ijki j k choices, the answer is (195)=11628\binom{19}{5} = 11628.

A simple generating functions argument is also possible. Let sn=i+j+k=nijks_n = \sum_{i + j + k = n} i j k. Then
n0snxn=(n0nxn)3=(x(1x)2)3=x3(1x)6 \sum_{n \geq 0} s_n x^n = \left(\sum_{n \geq 0} n x^n\right)^3 = \left(\frac{x}{(1-x)^2}\right)^3 = \frac{x^3}{(1-x)^6}
and so sn=(n+25)s_n = \binom{n+2}{5}, yielding s17=(195)s_{17} = \binom{19}{5}.

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.