Maths Olympiad Prep

Library / /608 of 860

Algebra Difficulty 5.3 AIME, harder Find the answer

Let a,b,c,d,ea, b, c, d, e be nonnegative integers such that 625a+250b+100c+40d+16e=153625 a+250 b+100 c+40 d+16 e=15^{3}. What is the maximum possible value of a+b+c+d+ea+b+c+d+e ?

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

Solution

The intuition is that as much should be in ee as possible. But divisibility obstructions like 1615316 \nmid 15^{3} are in our way. However, the way the coefficients 54>532>5^{4}>5^{3} \cdot 2>\cdots are set up, we can at least easily avoid having a,b,c,da, b, c, d too large (specifically, 2\geq 2 ). This is formalized below. First, we observe that (a1,a2,a3,a4,a5)=(5,1,0,0,0)(a_{1}, a_{2}, a_{3}, a_{4}, a_{5})=(5,1,0,0,0) is a solution. Then given a solution, replacing (ai,ai+1)(a_{i}, a_{i+1}) with (ai2,ai+1+5)(a_{i}-2, a_{i+1}+5), where 1i41 \leq i \leq 4, also yields a solution. Given a solution, it turns out all solutions can be achieved by some combination of these swaps (or inverses of these swaps). Thus, to optimize the sum, we want (a,b,c,d){0,1}4(a, b, c, d) \in\{0,1\}^{4}, since in this situation, there would be no way to make swaps to increase the sum. So the sequence of swaps looks like (5,1,0,0,0)(1,11,0,0,0)(1,1,25,0,0)(1,1,1,60,0)(1,1,1,0,150)(5,1,0,0,0) \rightarrow(1,11,0,0,0) \rightarrow (1,1,25,0,0) \rightarrow(1,1,1,60,0) \rightarrow(1,1,1,0,150), yielding a sum of 1+1+1+0+150=1531+1+1+0+150=153.

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.