Maths Olympiad Prep

Library / /599 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

We view choosing five objects from a row of 19 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=((6n3))=(n+25)s_{n}=\left(\binom{6}{n-3}\right)=\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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.