UncleEbenezer wrote:OLTB wrote:I try and try to understand the logic of how Gengulphus arrived at the answer and just can't get past the first paragraph of how the 'S' equals the number that it does (I won't reveal it here just in case others are working through it still).
Cheers, OLTB.
Just consider the range of five-digit numbers that can be the sum of any two 4-digit numbers. You can trivially get a minimum and a maximum. That's all Gengulphus did.
It's equivalent to what I did in that particular case, but how I actually did it was basically one particular case of a more general technique, and that more general technique is used quite a bit later in my solution, so is worth explaining:
Think about how you were (hopefully!) taught at school to do addition with pencil and paper. You start at the rightmost column and work your way leftwards. In the rightmost column, you add the two digits, then you note the bottom digit of the sum as the result digit in that column and the top digit (if it has one) as the carry into the next column to the left. Then you repeat the exercise for the next column to the left, except that you add the carry into that column (if any) into the sum as well as the two digits. And you continue working leftwards until you get to the leftmost column, where some of the columns will only have one digit if the numbers are of unequal length. Then finally you might have a carry into a new column to the left of the leftmost original column, in which case that carry out becomes the top digit of the result. As an example of that process, consider the addition 9813+748 = 10561:
Carries: 1 1 1 1 11 1 11 1
To add: 9813 9813 9813 9813 9813 9813
and: 748 748 748 748 748 748
----- ==> ----- ==> ----- ==> ----- ==> ----- ==> -----
Result: 1 61 561 0561 10561
Digit 3+8 1+1+4 8+7 1+9 final
sum is: = 11 = 6 = 15 = 10 step
That picture isn't ideal from the point of view of systematically analysing such additions, because there's actually a multitude of such pictures, depending on which carries exist and which don't. That would produce a multitude of cases in the analysis, i.e. in the solution of the sort of puzzle we're dealing with here - and the basic issue with finding solutions to such puzzles and many other mathematical puzzles is to find a non-brute-force solution, i.e. one that doesn't involve just looking at huge numbers of possibilities until one finds the one that works.
However, in this case we can deal with that very easily by regarding carries that don't actually exist as instead existing and being zero. And similarly, we can regard digits to the left of those that actually exist as instead existing and being zero, up to and including the potential column to the left of the leftmost column of the numbers being added. None of those zeros change any of the other digits, and they transform the above example into:
Carries: 1 01 101 1101 1101
To add: 09813 09813 09813 09813 09813 09813
and: 00748 00748 00748 00748 00748 00748
----- ==> ----- ==> ----- ==> ----- ==> ----- ==> -----
Result: 1 61 561 0561 10561
Digit 3+8 1+1+4 0+8+7 1+9+0 1+0+0
sum is: = 11 = 06 = 15 = 10 = 01
Or writing the final step of that more generally, with letters representing digits and carries so that we're not pinning it down to any particular addition, it becomes the following addition of two up-to-4-digit numbers NMLK and SRQP to form an up-to-5-digit sum ZYXWV:
Carries: dcba in which the individual column sums are:
K+P = aV
To add: 0NMLK a+L+Q = bW
and: 0SRQP b+M+R = cX
----- c+N+S = dY
Result: ZYXWV d+0+0 = Z
There are some things we can immediately deduce some things without any more information about the actual numbers, the most important of which is that every carry is either 0 or 1. That follows by observing that each digit is in the range 0 to 9, from which it follows that aV = K+P lies in the range 0 to 9+9 = 18, and thus that a is 0 or 1. It follows that bW = a+L+Q lies in the range 0 to 9+9+1 = 19, so b is also 0 or 1. That cascades to successively show that c and d are 0 or 1, and finally that d+0+0 lies in the range 0 to 1, so is adequately represented by a digit Z, not requiring any further carries leftwards, and indeed that Z can only be 0 or 1, not the full digit range 0 to 9. (This is of course something we could work out much less long-windedly by observing that NMLK and SRQP both lie in tha range 0 to 9999, so ZYXWV must lie in the range 0 to 2*9999 = 19998, as UncleEbenezer observes - but the point of the more long-winded route is that it also gives you the five 'column sum' equations, and those are basically used in the rest of my solution. Also note that part of the reason it is long-winded is that I have broken it down into quite small logical steps: most of the sequences of those steps are completely standard in dealing with addition-of-two-numbers alphametic puzzles and so usually described quite briefly - e.g. I said things like "looking at column 4" to indicate that I was talking about the 4th of the column sums.)
So now start pinning it down to our actual puzzle. To do this, first replace K, L, M, N, P, Q, R, S, V, W, X, Y and Z throughout by E, M, O, S, S, A, M, X, A, T, N, A and S respectively, doing one replacement only on each letter (e.g. original Ss become Xs, and original Ns become Ss, but the latter don't then get replaced further by Xs). We get:
Carries: dcba in which the individual column sums are:
E+S = aA
To add: 0SOME a+M+A = bT
and: 0XMAS b+O+M = cN
----- c+S+X = dA
Result: SANTA d+0+0 = S
Note by the way that the column sums (with the not-really-necessary zeros dropped) can be read off pretty easily from the original puzzle: it's basically just a matter of inserting the carries a, b, c, d into the columns they go to above the line and the columns they come from below the line, rotating left by 90 degrees and inserting the "+"s and changing the line into "="s:
Carries in: dcba ES|aA E+S=aA
SOME SOME aMA|bT a+M+A=bT
XMAS ==> XMAS ==> bOM|cN ==> b+O+M=cN
----- ----- cSX|dA c+S+X=dA
Carries out: dcba d | S d = S
SANTA SANTA
So as I indicated above, what you actually need to do is quite simple and can be described briefly: the above long-winded explanation is only there to explain
why it's the right thing to do.
The column sums are not all that is needed to solve the puzzle - we additionally need the information that:
* A, E, M, N, O, S, T, X are
distinct digits in the range 0 to 9, a standard convention for such puzzles;
* the leading digits (S of SOME and SANTA, and X of XMAS) are nonzero, another standard convention for such puzzles, so lie in the range 1 to 9;
* a, b, c and d are each either 0 or 1, as deduced above.
The first step of my solution is then a matter of combining the information that d is 0 or 1, S lies in the range 1 to 9, and d=S to deduce that d=S=1. Then the next step uses that to transform the column sum c+S+X = dA into c+1+X = 1A, which must be >= 10, so c+X >= 9, and since we know that c <= 1, that X >= 8 and so must be 8 or 9.
And so it goes on - one basically tries to whittle away at the puzzle, with each stage of whittling involving making a deduction from the column sums, the additional information and previous deductions. Ideally, each deduction tells you the exact value of a digit or carry, as the first step above does, and you progress through a sequence of such deductions until you know the exact values of all of them, at which point you've solved the puzzle. In practice, though, one often finds one can only make a deduction that there is a limited number of possibilities, but more than one, as in the second step above where one can deduce that there are the two possibilities X=8 and X=9. That's still an improvement from the position before the deduction, when all one knew about X's possible value was that it was in the range 0 to 9 and distinct from S=1, leaving nine possibilities. But we can't immediately narrow X's value down further - we first have to make deductions about other digits and carries (in my solution, first about c, then about A) and then we can revisit the question of X's value and eliminate one of the two possibilities, thus deducing X's exact value.
So basically, a solution of such an alphametic involves a sequence of deductions, starting with the column sums and the additional information, and with each building on previous deductions, and ending with the exact value of every digit and carry known: during the course of the solution, we may well have steps that increase the number of possibilities we're having to consider, but later stages will reduce it again and we'll end up with precisely one possibility (since if we end up with no possibilities, the alphametic doesn't have a solution, and if we end up with more than one, only one of them can be compatible with the alphametic's unique solution, implying that it's possible to make further deductions that eliminate the other possibilities).
For a well-posed alphametic (i.e. one that has a unique solution), there is always such a solution, namely the "brute force" solution: for this particular alphametic, that basically goes: there are 10 possibilities for A; for each of them, there are nine possibilities for E that are not equal to A, making 10*9 = 90 possibilities for the combination of A and E. For each of those, there are 8 possibilities for M that are not equal to either A or E, making 90*8 = 720 possibilities for the combination of A, E and M. And so on, eventually arriving at 10*9*8*7*6*5*4*3 = 1,814,400 possibilities for the combination of A, E, M, N, O, S, T and X. Then we can transform the column sum equations to make them tell us what all the carries are: E+S=aA becomes a = (E+S-A)/10 (remembering that the two digit number aA is equal to 10*a+A) and the next three become b = (a+M+A-T)/10, c = (b+O+M-N)/10 and d = (c+S+X-A)/10 similarly. Use those to successively calculate a, b, c and d for each of the 1,814,400 possibilities, and then check each possibility against all the constraints that aren't automatically satisfied by what we've done so far: the last column sum equation d = S, the no-leading-zeros requirements that neither S nor X is zero, and the requirements that each of a, b, c and d is 0 or 1. (Or indeed check each of them against
all of the requirements - this is brute force, after all!)
The possibilities that survive that elimination will be precisely the solutions of the alphametic. So this process, and more generally the analogous process for any well-posed alphametic, will find the alphametic's unique solution - hence my assertion that any well-posed alphametic has a solution of the type described above. Also, for any alphametic at all, this "brute force" technique will find all the solutions and so tell you whether the alphametic is well-posed.
Of course, working through a few million-plus possibilities is basically completely impossible for a human, and equally, there need to be
far more possibilities than that to be much of a challenge to a computer. So basically, the only things that are at all interesting about the "brute force" technique are that it shows that a chain-of-deductions-ending-at-the-answer always exists for a well-posed alphametic, and that it additionally allows one to check whether an alphametic is well-posed.
So IMHO the challenge of alphametics is not so much finding the answer, as doing it in a 'nice' way - one that doesn't branch out into too many possibilities at any stage. That is of course a somewhat fuzzy aim - how many is too many? - but it gives a general goal to aim for, of keeping the number of possibilities one is tracking during the solution down.
And the bigger challenge of alphametics is designing good ones rather than solving them. A good alphametic needs to be well-posed, wants to have a 'nice' solution that is challenging to find, and ideally uses words that match each other well. But unforunately those usually come into conflict with each other - for example, XMAS + GIFT = SANTA would use words that match each other especially well, but has lots of solutions (46 of them if I've counted correctly), including e.g. 3401 + 7289 = 10690 and 5241 + 8793 = 14034. So it's a long way from being a well-posed alphametic, and any way of solving it must branch out into at least 46 possibilities and so can hardly be very 'nice'...
Gengulphus