Maths Olympiad Prep

Library / Annual Harvard-MIT Mathematics Tournament /33 of 72

Annual Harvard-MIT Mathematics Tournament

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
∑n≥0snxn=(∑n≥0nxn)3=(x(1−x)2)3=x3(1−x)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,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.