Maths Olympiad Prep

Library / /159 of 168

Number theory Difficulty 2.7 Junior Find the answer

If NN is a positive integer between 1000000 and 10000000, inclusive, what is the maximum possible value for the sum of the digits of 25×N25 \times N?

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

Solution

Since NN is between 1000000 and 10000000, inclusive, then 25×N25 \times N is between 25000000 and 250000000, inclusive, and so 25×N25 \times N has 8 digits or it has 9 digits. We consider the value of 25×N25 \times N as having 9 digits, with the possibility that the first digit could be 0. Since 25×N25 \times N is a multiple of 25, its final two digits must be 00,25,5000,25,50, or 75. For a fixed set of leftmost three digits, xyzxyz, the multiple of 25 that has the largest sum of digits must be xyz999975xyz999975 since the next four digits are as large as possible (all 9s) and the rightmost two digits have the largest possible sum among the possible endings for multiples of 25. So to answer the question, we need to find the integer of the form xyz999975xyz999975 which is between 25000000 and 250000000 and has the maximum possible sum x+y+zx+y+z. We know that the maximum possible value of xx is 2, the maximum possible value of yy is 9, and the maximum possible value of zz is 9. This means that x+y+z2+9+9=20x+y+z \leq 2+9+9=20. We cannot have 299999975 since it is not in the given range. However, we could have x+y+z=19x+y+z=19 if x=1x=1 and y=9y=9 and z=9z=9. Therefore, the integer 199999975 is the multiple of 25 in the given range whose sum of digits is as large as possible. This sum is 1+6×9+7+5=671+6 \times 9+7+5=67. We note that 199999975=25×7999999199999975=25 \times 7999999 so it is a multiple of 25. Note that N=7999999N=7999999 is between 1000000 and 10000000.

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.