0
$\begingroup$

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:)

$\endgroup$
5
  • 1
    $\begingroup$ 'The solution is to observe the answer is 10010' – but how? How do you 'observe' the (possible) answer in $10010$? $\endgroup$
    – CiaPan
    Commented Aug 31, 2023 at 15:24
  • $\begingroup$ no,the answer said that,not mine.I am confused too. $\endgroup$
    – Student
    Commented Aug 31, 2023 at 15:28
  • 1
    $\begingroup$ Maybe , the solution was simply guessed or determined by computer help. The book only demonstrates that it is actually the smallest possibility. $\endgroup$
    – Peter
    Commented Aug 31, 2023 at 17:25
  • $\begingroup$ We require you to credit the original source of all text or problems that were initially authored by others: math.stackexchange.com/help/referencing. Please edit your question accordingly. $\endgroup$
    – D.W.
    Commented Aug 31, 2023 at 18:23
  • $\begingroup$ I don't think "Is there any other way to solve this?" is a useful question. There are typically an infinite number of ways to solve it. I could make a trivial change to the solution and then it would technically consistent a different way to solve it. If there is some specific reason you are dissatisfied with this answer, perhaps you can formulate a more specific question with specific requirements on what techniques are allowed to be used by the solution. $\endgroup$
    – D.W.
    Commented Aug 31, 2023 at 18:24

1 Answer 1

1
$\begingroup$

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:

$k_1 \mod 9$ $4 k_1 \mod 9$ $k_2 \mod 9$ $5 k_2 \mod 9$
1 4 8 4
2 8 7 8
3 3 6 3
4 7 5 7
5 2 4 2
6 6 3 3
7 1 2 1
8 5 1 5
9/0 9/0 9/0 9/0
  • 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .