Czech Republic Math Olympiad 2008 Problem

In decimal representation, we call an integer k-carboxylic if and only if it can be represented as a sum of k distinct integers, all of them greater than 9, whose digits are the same. For instance, 2008 is 5-carboxylic because $2008 = 1111 + 666 + 99 + 88 + 44$. Find, with an example, the smallest integer k such that 8002 is k-carboxylic.

I started by writing $8002 = 1111a + 111b + 11c$. To minimize k, we want to maximize a, then b and c. But it seems there are still a lot of combinations. Help?

• You are implicitly assuming you can do it with just 3 parameters $a,b,c$. This need not be true, as suggested by the example they gave for 2008. You may need several distinct contributions from multiples of 1111; and 111; and 11. Nov 12, 2013 at 19:35
• There is not really any difference so long as you step back and allow $a,b,c$ to be any integer between $0$ and $9$ inclusive. Obviously, you can't have a series of more than $4$ $1$'s. If the smallest number $k$ you seek for example where to be $2$, then this is the case where $b=0$ or $c=0$. So approaching from this problem is not necessarily bad. Nov 12, 2013 at 19:53
• @mathematics2x2life Except as Daniel's answer and my statement say, in general you will require several distinct multiples of 11, and possibly even 111. It's not a 3-carboxylic number, so you're going to need several of at least one of them. Nov 12, 2013 at 21:11

Since we have only multiples of $11$, $111$, and $1111$ to consider, it is relatively easy. $1111$ is a multiple of $11$, so we can determine the required number of $111$s (modulo $11$) immediately, $b \equiv 8002 \pmod{11}$, which tells us $b \equiv 5 \pmod{11}$.
For the remaining $8002 - 555 = 7447$, we use $6666$, and for the remainder $781 = 71\cdot 11$, we use $7$ times $99$ plus $88$ for a total of $10$ summands.
It is then easy to check that we don't get fewer summands if we try $b = 16$, which requires two three-digit summands, or $b = 27$, which requires three three-digit summands, or $b = 38, \, 49,\, \dotsc$, so indeed $10$ is the minimal $k$ for which $8002$ is $k$-carboxylic.