# Find the smallest possible checksum

What is the smallest possible checksum $$C_{min}$$ of the sum of two three-digit numbers $$N_1$$ and $$N_2$$ that are formed from the six given digits 2, 3, 4, 5, 7 and 9 (each digit shall be used only once). The checksum of a number is defined as the sum of its digits. What are the sums that have this smallest possible checksum $$C_{min}$$?

Here my thoughts: I believe that the smallest checksum is 3. I obtained this by simple reasoning: With $$3 + 7 = 10$$ there is 0 in the sum and a carry-over "1". Then, with $$4 + 5 = 9$$ and the carry-over "1" we obtain another "0" in the sum, creating another carry-over "1". Finally, $$2 + 9 = 11$$, and with the carry-over it is "12". Thus, the checksum is $$1 + 2 + 0 + 0 = 3.$$ But is it right?

Examples:

$$243 + 957 = 1200,$$ checksum = 3

$$423 + 597 = 1020,$$ checksum = 3

If the answer is at all correct, how can I prove that it is? And then, how would I be able to find all the sums of numbers? My approach: Permute the given checksum, and check if I can find N1 and N2 that have this result.

There must be a more systematic or rigorous approach, I would believe. Perhaps someone can guide me on this. Thank you.

• You don't give a rigorous definition of the checksum that you're using. Do you mean "find the smallest digit sum of $a + b$ when $a, b$ are two three-digit numbers formed from the six given digits $2, 3, 4, 5, 7, 9$?" – orlp Oct 2 '18 at 12:20
• Sorry, I mean the sum over the digits. Will edit my post.If the numbers N1 and N2 are 539 and 247, their sum is 786 and the checksum of the sum is 7 + 8 + 6 = 21 – Parzifal Oct 2 '18 at 12:23
• I'm not posting this as an answer as it's a mathematics site, but there is a systematic way: check each case with a computer. Since $6! = 720$ this happens in the blink of an eye and indeed confirms $3$ is the smallest possible digit sum. – orlp Oct 2 '18 at 12:26
• Are you familiar with the notion of casting out nines? – Barry Cipra Oct 2 '18 at 12:26
• No - what do you mean by casting out nines? – Parzifal Oct 2 '18 at 12:29

Let's start with a brief explanation of "casting out nines" as it's needed for the problem at hand. If $$ABCD$$ is the (at most) four-digit sum of a pair of three-digit numbers, $$abc+def$$, then, since $$1000\equiv100\equiv10\equiv1$$ mod $$9$$, we have

\begin{align} A+B+C+D &\equiv(1000A+100B+10C+D)\\ &=(100a+10b+c)+(100d+10e+f)\\ &\equiv a+b+c+d+e+f\mod 9 \end{align}

so, if $$\{a,b,c,d,e,f\}=\{2,3,4,5,7,9\}$$, we have

$$A+B+C+D\equiv2+3+4+5+7+9=(2+7)+3+(4+5)+9\equiv3\mod 9$$

which means that the digit sum for any pair $$abc+def$$ belongs to $$\{3,12,21,\ldots\}$$. The OP has already found one example with digit sum $$3$$, namely $$243+957=1200$$, so we can conclude that the smallest possible digit sum is $$3$$. The remaining question, how many different pairs give digit sum $$A+B+C+D=3$$?

Note that

$$abc+def=dbc+aef=aec+dbf=dec+abf$$

so it suffices to count the number of solutions with $$a\lt d$$, $$b\lt e$$ and $$c\lt f$$ and then multiply by $$4$$ (or by $$8$$, if you want to distinguish $$(abc,def)$$ from $$(def,abc)$$). Now the only realistic possibilities for $$ABCD$$ are $$1200$$, $$1020$$, $$1002$$, $$1110$$, $$1101$$, and $$1011$$. (That is, $$500\lt abc+def\lt2000$$, so we must have $$A=1$$ since $$A=0$$ would imply $$B\ge5$$.) Let's consider these possibilities according to what's in the ones place.

If $$D=0$$ (i.e., if $$ABCD=1200$$, $$1020$$, or $$1110$$), we can only have $$c=3$$ and $$f=7$$, which will carry a $$1$$ into the tens place. That makes $$C=1$$ impossible, but it gives $$1+2+9=11$$ and $$1+4+5=10$$ as possibilities for $$C=2$$ and $$C=0$$. Indeed, we get x two solutions (with $$a\lt d$$, etc.), namely $$423+597=1020$$ and $$243+957=1200$$.

If $$D=1$$ (i.e., if $$ABCD=1101$$ or $$1011$$), we can have $$c+f=2+9=11$$ or $$c+f=4+7=11$$. In either case the carried $$1$$ from $$c+f$$ means we need $$b+d=9$$ or $$10$$ in order to get $$C=0$$ or $$1$$. For $$c+f=2+9$$, both values of $$C$$ are attainable, each in only one way: $$342+759=1101$$ and $$432+579=1011$$. For $$c+f=4+7$$, neither value of $$C$$ is attainable, since the only digits that sum to $$9$$ are $$2+7$$ and $$4+5$$ and, as already remarked, the only digits that sum to $$10$$ is $$3+7$$. Thus we get just two solutions with $$D=1$$, namely $$342+759=1101$$ and $$432+579=1011$$.

Finally, if $$D=2$$ (i.e., $$ABCD=1002$$), we can only have $$c+f=3+9$$ or $$c+f=5+7$$. In either case we'll need $$b+e=9$$, which is possible only as $$2+7$$ or $$4+5$$. If $$c+f=3+9$$, either of these is possible, while neither is possible if $$c+f=5+7$$. So again we get just two solutions, namely $$243+759=1002$$ and $$423+579=1002$$.

Altogether we get six solutions with $$a\lt d$$, $$b\lt e$$ and $$c\lt f$$:

\begin{align} 423+579&=1020\\ 243+957&=1200\\ 342+759&=1101\\ 432+579&=1011\\ 243+759&=1002\\ 423+579&=1002 \end{align}

The total count, without the restrictions $$a\lt d$$ and $$b\lt e$$, is thus $$24$$; removing the restriction $$c\lt f$$ brings the total number of solutions to $$48$$.

• Thank you for the comprehensive and very well explained answer. Insightful. Much appreciate the time you took! – Parzifal Oct 4 '18 at 11:04

Hint1:

$$\sum_{k=0}^n 10^ka_k \equiv \sum_{k=0}^n a_k \mod{9}$$

Hint2:

Note, that the digital root for your numbers is always the same, regardless of your choice.

• Thanks, I checked your link but I do not understand how your hint leads to the solution. Can you elaborate a bit, please? – Parzifal Oct 2 '18 at 12:53
• @Parzifal I've added one more hint. – Jaroslaw Matlak Oct 2 '18 at 13:08
• So indeed, the digital root always is 12. This means that any combination of the digits will yield this root. And I always get to this root as the minimum digital sum by re-applying the casting out of nines ... the argumentation runs in this direction? – Parzifal Oct 2 '18 at 13:36
• * Digital root is one-digit number, in this case $3$. * The control sum is equal to the digital root (mod 9). Therefore the control sum can't be smaller than the digital root. You've found the number with control sum equal to the digital root, so... – Jaroslaw Matlak Oct 2 '18 at 18:27
• Thank you - your comments and hints were very helpful to me. First time that I came across such concepts. – Parzifal Oct 2 '18 at 19:22

Building on the helpful hints of @Jaroslaw Matlak, the digital root of the sum will equal the digital root of the sum of the digital roots for the summed numbers. Consider your first example:

$$243 + 957 = 1200$$

The digital root of $$243$$ is

$$2+4+3 = 9$$

and the digital root of $$957$$ is

$$9 + 5 + 7 = 21,$$ continuing to sum until we have one digit, $$2+1 = 3$$.

So the sum of the digital roots for $$243$$ and $$957$$ is $$9+3 = 12$$ giving $$1+2 = 3$$. This is equal to the digital root of $$1200$$.

$$1+2+0+0 = 3$$.

You should see that the actual permutations of the numbers $$2,3,4,5,7,9$$ don't matter in the calculation of the digital root. The left hand side digital root will always be $$2+3+4+5+7+9=30$$, $$3+0=3$$, the same as the digital root of the sum.

The other answers have shown that the digit sum will converge to $$3$$ if you repeat it enough. It appears you only want to take the digit sum once, so you can get $$3,12,21$$. Once you find an example with $$3$$ you are done. Finding such an example can be done with clever searching. There is only one pair of digits, $$3,7$$, available that sum to $$10$$, so we put those in the ones place to get a $$0$$. There is another pair, $$4,5$$, that sum to $$9$$ so if they are added with a carry in you will get another $$0$$. The sum of two three digit numbers cannot have more than four digits, so if you get two zeros the digit sum has to be $$3$$ or $$12$$, but since the carry into the thousands is $$1$$ you can only get $$3$$. Good work.

• Milikan: That is how I actually searched but I lacked the proof. I learned a lot from you all. And about finding all possible sums - is my suggested approach ok? Thanks – Parzifal Oct 2 '18 at 14:33
• What you would usually permute is the digits in the sum and see what checksums come out. If you try all the possibilities (there are only $360$) you will get them all. We have $3$. It is easy to get $12$ from $243+957$ and $21$ from $342+957$. The sum of all the digits is $30$ and you can't avoid a carry, so I believe $30$ is impossible but I haven't proven it. – Ross Millikan Oct 2 '18 at 15:03
• How aout $439+572$? – Barry Cipra Oct 2 '18 at 15:11
• @Barry Cipra: Good one (CS=1101). But can I rule out 1110 and 1011 apart from trying out all possibilities? – Parzifal Oct 2 '18 at 15:46
• @Ross Milikan: Thank you for your time explaining, I appreciate this very much. I´ll try my luck (but as Barry Cipra points out, it´s not an "easy" task). – Parzifal Oct 2 '18 at 15:49