Maths Olympiad Prep

Library / /6 of 11

Combinatorics Difficulty 6.0 AIME, harder Prove it Argentina

Find the sum of all products a1a2a50a_1a_2 \cdots a_{50} where a1,a2,,a50a_1, a_2, \ldots, a_{50} are distinct positive integers not exceeding 101101 and such that no two of them have sum 101101.

Solution

We distinguish between two cases for an admissible 5050-tuple a1,a2,,a50a_1, a_2, \ldots, a_{50}.

a) If no aia_i is equal to 101101 then a1,a2,,a50a_1, a_2, \ldots, a_{50} contains exactly one number from every pair (i,101i)(i, 101-i), 1i501 \le i \le 50. Hence there are 2502^{50} choices for a1,a2,,a50a_1, a_2, \ldots, a_{50}, and each respective product a1a2a50a_1a_2 \cdots a_{50} appears exactly once in the expansion of the product
P=(1+100)(2+99)(50+51)=10150. P = (1 + 100)(2 + 99) \cdots (50 + 51) = 101^{50}.

b) If one of the aia_i is 101101 then the remaining ones come from 4949 different pairs (i,101i)(i, 101-i), 1i501 \le i \le 50. Suppose that pair (1,100)(1, 100) is not present. There are 2492^{49} such products a1a2a50a_1a_2 \cdots a_{50}, the summands in the expansion of the P1=101(2+99)(50+51)=10150P_1 = 101(2+99)\cdots(50+51) = 101^{50}. Analogously if the non-represented pair is (2,99)(2, 99), (3,98)(3, 98), \dots, (50,51)(50, 51) the respective products appear once in the expansions of
P2=(1+100)101(3+98)(50+51)=10150, P3=(1+100)(2+99)101(50+51)=10150,\multicolumn2lP50=(1+100)(2+99)(49+52)101=10150. \begin{align*} P_2 &= (1 + 100)101(3 + 98)\cdots(50 + 51) = 101^{50}, \ P_3 &= (1 + 100)(2 + 99)101\cdots(50 + 51) = 101^{50}, \\ \multicolumn{2}{l}{\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots} \\ P_{50} &= (1 + 100)(2 + 99)\cdots(49 + 52)101 = 101^{50}. \end{align*}
By a) and b) the sum in question is 10150+5010150=5110150101^{50} + 50 \cdot 101^{50} = 51 \cdot 101^{50}.

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.