Maths Olympiad Prep

Library / /32 of 121

, 2004

Combinatorics Difficulty 5.6 AIME, harder Prove it India

Problem:
Prove that the number of 5-tuples of positive integers (a,b,c,d,e)(a, b, c, d, e) satisfying the equation
abcde=5(bcde+acde+abde+abce+abcd) a b c d e = 5(b c d e + a c d e + a b d e + a b c e + a b c d)
is an odd integer.

Solution

Solution:
We write the equation in the form:
1a+1b+1c+1d+1e=15 \frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d} + \frac{1}{e} = \frac{1}{5}
The number of five tuples (a,b,c,d,e)(a, b, c, d, e) which satisfy the given relation and for which aba \neq b is even, because if (a,b,c,d,e)(a, b, c, d, e) is a solution, then so is (b,a,c,d,e)(b, a, c, d, e) which is distinct from (a,b,c,d,e)(a, b, c, d, e). Similarly, the number of five tuples which satisfy the equation and for which cdc \neq d is also even. Hence it suffices to count only those five tuples (a,b,c,d,e)(a, b, c, d, e) for which a=ba = b, c=dc = d. Thus the equation reduces to
2a+2c+1e=15 \frac{2}{a} + \frac{2}{c} + \frac{1}{e} = \frac{1}{5}
Here again, the tuple (a,a,c,c,e)(a, a, c, c, e) for which aca \neq c is even because we can associate a different solution (c,c,a,a,e)(c, c, a, a, e) to this five tuple. Thus it suffices to consider the equation
4a+1e=15 \frac{4}{a} + \frac{1}{e} = \frac{1}{5}
and show that the number of pairs (a,e)(a, e) satisfying this equation is odd.
This reduces to
ae=20e+5a a e = 20 e + 5 a
or
(a20)(e5)=100 (a - 20)(e - 5) = 100
But observe that
100=1×100=2×50=4×25=5×20=10×10=20×5=25×4=50×2=100×1 \begin{aligned} & 100 = 1 \times 100 = 2 \times 50 = 4 \times 25 = 5 \times 20 \\ & \quad = 10 \times 10 = 20 \times 5 = 25 \times 4 = 50 \times 2 = 100 \times 1 \end{aligned}
Note that no factorisation of 100100 as product of two negative numbers yields a positive tuple (a,e)(a, e). Hence we get these 99 solutions. This proves that the total number of five tuples (a,b,c,d,e)(a, b, c, d, e) satisfying the given equation is odd.

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.