Find the smallest positive integer which can be written
both as (i) a sum of $2002$ positive integers (not necessarily distinct), each of which has the same sum of digits and (ii) as a sum of $2003$ positive integers (not necessarily distinct), each of which has the same sum of digits.
The book's solution is to 'observe' the answer is $10010$:$$ 10010 = 2002·5 = 1781·4+222·13$$ and prove it is the minimal integer.
The answer is $10010$. First observe that this is indeed a solution: $$10010 = 2002·5 = 1781·4+222·13$$ so we may express $10010$ as the sum
of $2002$ fives or of $1781$ fours and $222$ thirteens, where $1781+222 = 2003$. To
prove minimality, observe that a number is congruent modulo $9$ to the sum of its digits, so two positive integers with the same digit sum are in the same residue class modulo $9$. Let $k_1$ be the digit sum of the $2002$ numbers and $k_2$ the digit sum of the $2003$ numbers. Then $$4k_1 ≡ 2002k_1 ≡ 2003k_2 ≡ 5k_2
\pmod 9$$ If $k_1 ≥ 5$, the sum of the $2002$ numbers is at least $10010$; if $k_2 ≥ 5$, the sum of the $2003$ numbers is greater than $10010$. However, the solutions
$$k_1 ≡ 1, 2, 3, 4 \pmod 9$$ give $k_2 ≡ 8, 7, 6, 5$, respectively, so that at least one of $k_1$ or $k_2$ is greater than or equal to $5$, and the minimal integer is $10010$.
My question: Is there any other way to solve this? If it isn't, what is the quickest way to find that $10010$ is the minimal integer which can be written both as (i) a sum of $2002$ positive integers (not necessarily distinct), each of which has the same sum of digits and (ii) as a sum of $2003$ positive integers (not necessarily distinct).
Any help?Thanks in advance:)
Best Answer
Technically, the solution given has all the components needed to solve the problem, but they're laid out in an order that makes sense from a succinct proof perspective rather than a "looking for the solution" perspective.
If we were solving the problem from scratch, then the order of operations might look something more like this:
Investigate the digit sums modulo 9. Notice that $4 k_1 \equiv 5 k_2 \mod 9$.
Write out the multiplication tables for 4 and 5, modulo 9, and pair the values up:
Notice that $k_1 + k_2 \equiv 0 \mod 9$, and as a result we will always have either $k_1 \geq 5$ or $k_2 \geq 5$.
Since the smallest number with a digit sum of $k$ is $k$ itself, that means that the smallest candidates we can consider are the ones of the form $2002k$ and $2003k$ where $k \geq 5$.
Starting with the smallest of these we have $2002 \times 5 = 10010$, and we want to see if we can express it as the sum of 2003 numbers with a digit sum congruent to 4 mod 9.
The most obvious way to do this would be to have some linear combination of 4 and 13, so we just have to solve the simultaneous equations $4m + 13n = 10010$ and $m + n = 2003$, giving $m = 1781, n = 222$, which provides our solution.
Now, if that hadn't worked, we might have had to experiment with finding solutions using 4, 13 and 22 (or maybe even including 31 and 40), or checking numbers with digit sum 13, or somehow proving that 10010 isn't a valid solution and moving up to $2003 \times 5 = 10015$, but thankfully the question was designed to avoid that messiness.