1
$\begingroup$

If you take a problem of the form:

 abc
+def
----
ghij

where each letter must be replaced by a different digit (that is, all digits, 0-9 must be used once), how many answers are there? I know of at least a few, but is there a way to find all of them without brute forcing the problem?

One possible answer is:

342+756=1098

can you find all the others?

Clarification: No leading zeros, please! (i.e. g, a, and d must not be 0)

Improve this question
$\endgroup$
4
  • $\begingroup$ Leading zeroes allowed? $\endgroup$
    – Beastly Gerbil
    May 23, 2017 at 19:44
  • 3
    $\begingroup$ I used a computer, and there are 96 possible answers. I think this may be a bit broad $\endgroup$
    – Beastly Gerbil
    May 23, 2017 at 19:46
  • $\begingroup$ good question @BeastlyGerbil , I'm gonna go ahead and say no leading zeros. And it might be too broad, hmmm. I was just wondering if there was a good algorithm for finding all of them without brute forcing it, but if there are that many maybe there isn't? $\endgroup$
    – MMAdams
    May 23, 2017 at 20:00
  • $\begingroup$ a priori, why would there be a reason for an algorithm to exist? $\endgroup$
    – Wen1now
    May 23, 2017 at 21:16

2 Answers 2

Reset to default
3
$\begingroup$

Partial answer / possible strategy.

Let's say we have a solutions.
Just by interchanging c with f we get an other solution.
The same goes if we change b and e or a and d.
This means that the total number of solutions is a multiple of $2 \times 2 \times 2 = 8$

now finding the solutions:

A place to start would be to group 1 and 0 to form 10 and look for combinations in the numbers 2 to 10 (9 numbers) in such a way that 2 numbers add up to a third one. So we don't get any carry over except in the hundreds place.
This way we get at least 2 solutions (without interchanging digits between numbers) for a combination because since there is no carry over we can switch the tenths with the units (inside both the numbers in the addition)
Such a solutions would be:
$5 + 4 = 9$, $2+6 = 8$ and $7+3 = 10$
So we get the solutions: $725 + 364 = 1089$ and $752 + 346 = 1098$.
based on the logic above we now have $2 \times 8 = 16$ solutions.
An other combination would be:
$3+5 = 8$, $7+2 = 9$ and $4+6 = 10$.
So we get the solutions:
$473 + 625 = 1098$ and $437 + 652 = 1089$ and the additional solutions obtained from interchanging values (16 in total).
So now we have at least $16 + 16 = 32$ solutions.

Next step.

g is clearly 1 since we can get a carry over of max 1 from the hundreds place.
So we are left with the digits 0 and 2 to 9 (9 digits) to group them in such a way that at least 2 of them (but not just the ones we place in the hundreds place) add up over 10 so we get a carry over so we can get different solutions from the case above.

One possible way of doing so:

$9+4 = 13$ (units place), $6+8 = 14$ (tenths place and we get a carry over from the units place so we end up with 15) and $7+2 = 9$ (on the hundreds place and we get the carry over from the tenths to reach 10).
The solutions is:
$769 + 284 = 1053$ and by interchanging the digits we get 8 solutions in total. Now we have 40.

This can go on until we find all possible combinations.

Indeed using a computer (sorry for that, but I got tired of blindly stabbing for solutions) you get 96 total solutions. Which matches my finding that the total number is a multiple of 8.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is an extremely well thought out answer! Thank you! So, I guess there's kind of 12 "unique" answers and then 8 permutations of those then. $\endgroup$
    – MMAdams
    May 24, 2017 at 13:32
  • $\begingroup$ I guess so. The math does not lie. $\endgroup$
    – Marius
    May 24, 2017 at 14:38
1
$\begingroup$

If A=7 B=8 C=9 D=2 E=4 F=6 then G=1 H=0 I=3 J=5 

 789    
+246
----  
1035

If A=7 B=8 C=6 D=2 E=4 F=9 then G=1 H=0 I=3 J=5 

 786    
+249
---- 
1035

I just tried for these 2 answers, I think still there are many possibilities.

Improve this answer
$\endgroup$
5
  • $\begingroup$ See my comment there are another 94 ways $\endgroup$
    – Beastly Gerbil
    May 23, 2017 at 20:53
  • $\begingroup$ Okay, Based on condition (No leading zeros), How can you know still 94. I don't know exact count I am just asking? $\endgroup$
    – CR241
    May 23, 2017 at 21:01
  • $\begingroup$ Just try all permutations. There are 10 letters, so there are 10! possible permutaions. That's only about 3.6 million evaluations, which your computer can handle very quickly. $\endgroup$
    – M Oehm
    May 24, 2017 at 5:31
  • $\begingroup$ @MOehm no-computers tag though $\endgroup$
    – Beastly Gerbil
    May 24, 2017 at 6:11
  • $\begingroup$ @BeastlyGerbil: I've sen the tag. That comment was a reply to the question in CR241's comment. I share your criticism that the question is too broad (and probably not very interesting) when the right thing to do [tm] is to throw computing power at it. $\endgroup$
    – M Oehm
    May 24, 2017 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.