Maths Olympiad Prep

Library / /29 of 128

Combinatorics Difficulty 5.0 AIME, harder Prove it Philippines

Problem:
How many ordered quadruples (a,b,c,d)(a, b, c, d) of positive odd integers are there that satisfy the equation a+b+c+2d=15a + b + c + 2d = 15?

Solution

Solution:
Using the substitution (a,b,c,d)=(2a1+1,2b1+1,2c1+1,2d1+1)(a, b, c, d) = (2a_1 + 1, 2b_1 + 1, 2c_1 + 1, 2d_1 + 1) where a1,b1,c1,d1a_1, b_1, c_1, d_1 are nonnegative integers, the problem is equivalent to finding the number NN of nonnegative integer solutions of 2a1+1+2b1+1+2c1+1+4d1+2=152a_1 + 1 + 2b_1 + 1 + 2c_1 + 1 + 4d_1 + 2 = 15 or a1+b1+c1+2d1=5a_1 + b_1 + c_1 + 2d_1 = 5. Note that d12d_1 \leq 2, and for each fixed d1{0,1,2}d_1 \in \{0, 1, 2\}, the number of nonnegative integer solutions of a1+b1+c1=52d1a_1 + b_1 + c_1 = 5 - 2d_1 is (72d12)\binom{7 - 2d_1}{2}. Hence
N=d1=02(72d12)=(72)+(52)+(32)=21+10+3=34 N = \sum_{d_1 = 0}^{2} \binom{7 - 2d_1}{2} = \binom{7}{2} + \binom{5}{2} + \binom{3}{2} = 21 + 10 + 3 = 34

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.