Let be nonnegative integers such that . What is the maximum possible value of ?
Solution
The intuition is that as much should be in as possible. But divisibility obstructions like are in our way. However, the way the coefficients are set up, we can at least easily avoid having too large (specifically, ). This is formalized below. First, we observe that is a solution. Then given a solution, replacing with , where , 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 , since in this situation, there would be no way to make swaps to increase the sum. So the sequence of swaps looks like , yielding a sum of .
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.