## Santa

cinelli
2 Lemon pips
Posts: 167
Joined: November 9th, 2016, 11:33 am
Has thanked: 42 times
Been thanked: 21 times

### Santa

Two days late but still within the Christmas period. Here is a seasonal alphametic:
`' SOME XMAS -----SANTA`

Cinelli

Gengulphus
Lemon Quarter
Posts: 2422
Joined: November 4th, 2016, 1:17 am
Been thanked: 1121 times

### Re: Santa

cinelli wrote:Two days late but still within the Christmas period. Here is a seasonal alphametic:
`' SOME XMAS -----SANTA`

Spoiler...

Number the columns of the addition 1 to 5 from right to left.

First, by the usual no-leading-zeros convention for such puzzles, the S of SANTA is not zero and is the sum of two unwritten zeros in column 5 and the carry out of column 4. The only possibility is that S=1 and the carry out of column 4 is 1, which together imply via column 4 that X must be 8 or 9.

Next, compare columns 1 and 4. Column 1 shows that E + 1 has a ones digit of A, while column 4 shows that X + 1 + (carry out of column 3) also has a ones digit of A. If the carry out of column 3 were 0, those would together show that X = E, so the carry out of column 3 must be 1, and so column 4 shows that X + 2 has a ones digit of A. Since X = 8 or 9, X + 2 must be 10 or 11, implying that A is 0 or 1, and A cannot be 1 because S=1. So A=0, from which it quickly follows that X=8 and E=9.

Time to look at progress so far:
`  1OM9 8M01 -----10NT0`

The remaining digits M, N, O and T must all be in the range 2 to 7, and column 2 shows that T = M+1, which must have a carry out of 0 and also implies that M cannot be 7. So column 3 shows that N = M+O-10, since it's required to produce a carry out of 1. The available digits allow M+O to be at most 6+7 = 13 and M+O = 13 is in fact impossible: M is not 7 and so it can only arise from M=6, O=7, but that would imply that T=7, duplicating O. So M+O is at most 12, implying that N = M+O-10 is at most 2. But the available digits also imply that N is at least 2. So N=2 and M+O = 12. Since M is not 7, the only possibility is M=5, O=7, from which it follows that T = M+1 = 6, completing the solution:
`  1759 8501 -----10260`

Gengulphus

cinelli
2 Lemon pips
Posts: 167
Joined: November 9th, 2016, 11:33 am
Has thanked: 42 times
Been thanked: 21 times

### Re: Santa

Well solved, Gengulphus.

Cinelli

OLTB
Lemon Slice
Posts: 760
Joined: November 4th, 2016, 9:55 am
Has thanked: 606 times
Been thanked: 229 times

### Re: Santa

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

I have never been able to answer the questions set here (apart from the majority (not all) of the Christmas cryptics!) but I really like reading the questions and answers set on this board as I would like to improve my logical thought process, but this just baffles me. I will keep reading the answers though as I'm sure one day it will 'click'!

Cheers, OLTB.

SteelCamel
Posts: 28
Joined: February 15th, 2017, 5:49 pm
Been thanked: 9 times

### Re: Santa

I can never complete these, but the starting point is quite a common one.

"First, by the usual no-leading-zeros convention for such puzzles" - the convention is that a leading zero is shown as a blank, not a letter. So S is not zero, and neither is X.

The non-obvious bit is that we're only adding two numbers here. Ignoring what letters actually appear, the right-most column could total at most 18, if both the numbers in this column were 9s. The next column could total at most 19, with two 9s and a carry in of 1. The same applies to the next, and the next. There is no way for a carry of more than 1 to arise in this puzzle, whatever the arrangement of letters.

The sum of the left-most column is S, which equals (blank) plus (blank) plus the carry from the previous column - i.e just the carry from the previous column. The carry can be zero or one, so S can be zero or one - but we already saw it can't be zero, so S=1 is all that's left.

UncleEbenezer
Lemon Quarter
Posts: 2673
Joined: November 4th, 2016, 8:17 pm
Has thanked: 263 times
Been thanked: 361 times

### Re: Santa

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.

OLTB
Lemon Slice
Posts: 760
Joined: November 4th, 2016, 9:55 am
Has thanked: 606 times
Been thanked: 229 times

### Re: Santa

SteelCamel wrote:I can never complete these, but the starting point is quite a common one.

"First, by the usual no-leading-zeros convention for such puzzles" - the convention is that a leading zero is shown as a blank, not a letter. So S is not zero, and neither is X.

The non-obvious bit is that we're only adding two numbers here. Ignoring what letters actually appear, the right-most column could total at most 18, if both the numbers in this column were 9s. The next column could total at most 19, with two 9s and a carry in of 1. The same applies to the next, and the next. There is no way for a carry of more than 1 to arise in this puzzle, whatever the arrangement of letters.

The sum of the left-most column is S, which equals (blank) plus (blank) plus the carry from the previous column - i.e just the carry from the previous column. The carry can be zero or one, so S can be zero or one - but we already saw it can't be zero, so S=1 is all that's left.

Thanks SteelCamel - that extra explanation helps enormously!

Cheers, OLTB.

Gengulphus
Lemon Quarter
Posts: 2422
Joined: November 4th, 2016, 1:17 am
Been thanked: 1121 times

### Re: Santa

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=dACarries 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

OLTB
Lemon Slice
Posts: 760
Joined: November 4th, 2016, 9:55 am
Has thanked: 606 times
Been thanked: 229 times

### Re: Santa

Gengulphus wrote:

Gengulphus

Gengulphus - thank you so much for the time and effort in explaining the process to me - it really is appreciated (as are your HYP comments) and I'll sit down in a dark room and have a go at the next puzzle.

Cheers, OLTB.

OLTB
Lemon Slice
Posts: 760
Joined: November 4th, 2016, 9:55 am
Has thanked: 606 times
Been thanked: 229 times

### Re: Santa

p.s. OLTB is not an alphametic...

cinelli
2 Lemon pips
Posts: 167
Joined: November 9th, 2016, 11:33 am
Has thanked: 42 times
Been thanked: 21 times

### Re: Santa

I thought OLTB might like another ...

Solve

`(AN)^5 = EQUATION`

Cinelli

modellingman
2 Lemon pips
Posts: 184
Joined: November 4th, 2016, 3:46 pm
Has thanked: 33 times
Been thanked: 60 times

### Re: Santa

Spoiler

[color=#BFFFFF]Under the usual assumptions EQUATION is an 8 digit number so greater than 10^7 and less than 10^8, so 10^7 < (AN)^5 < 10^8,
hence 10^(7/5) < AN < 10^(8/5).
10^(7/5) is approx 25.1 and 10^(8/5) is approx 39.8 so AN must fall within the range 26 to 39, ie 14 possibilities.

These 14 possibilities for AN and their 5th powers [(AN)^5] are listed below

AN (AN)^5
== ========
26 11881376
27 14348907
28 17210368
29 20511149
30 24300000
31 28629151
32 33554432
33 39135393
34 45435424
35 52521875
36 60466176
37 69343957
38 79235168
39 90224199

The 8 digits in EQUATION are all different from each other. Only one of the 14 possibilities has this characteristic in its 5th power and the solution is therefore

(38)^5 = 79235168

I did at first think that there might be some way of narrowing down the possibilities by expanding (10*A + N)^5.
(AN)^5 = EQUATION then yields the result that N^5 (mod 10) = N.
However, this result holds true for all values of N from 0 to 9, so not a help.

[/color]

modellingman
2 Lemon pips
Posts: 184
Joined: November 4th, 2016, 3:46 pm
Has thanked: 33 times
Been thanked: 60 times

### Re: Santa

(AN)^5 = EQUATION

Could have been expressed as (AN)^T = EQUATION.

This would have been more difficult to solve but might have lead the solver to the only other puzzle where a 2 digit number raised to the power of a single digit results in an 8 digit number with all digits different. That puzzle is

(UT)^O = EQUATION

or

(UT)^6 = EQUATION

as a possibly easier alternative

OLTB
Lemon Slice
Posts: 760
Joined: November 4th, 2016, 9:55 am
Has thanked: 606 times
Been thanked: 229 times

### Re: Santa

cinelli wrote:I thought OLTB might like another ...

Solve

`(AN)^5 = EQUATION`

Cinelli

Thank you Cinelli - could I ask a few questions as my maths education stopped after my 'O' levels...

I think that ^5 next to the (AN) means 'to the power of' - is that right? Gengulphus commented on a post of mine on the HYP board last year when I was trying to work out a compounding return and I think he used that symbol then (I may be wrong!).

The A and the N can't be '0' as if you multiplied any number by 0, or 'to the power of' you get 0.

The numbers represented by A and N in (AN) have to be multiplied together i.e. A x N and then that number 'to the power of' 5 totals the number represented by EQUATION, which is an eight figure sum. The number '5' is not in EQUATION as you have already put it next to (AN).

Thanks for your patience! Cheers, OLTB.

cinelli
2 Lemon pips
Posts: 167
Joined: November 9th, 2016, 11:33 am
Has thanked: 42 times
Been thanked: 21 times

### Re: Santa

Hi OLTB,

I will have a go at answering your questions. You are quite right is saying that the symbol ^ means "raise to the power of". For instance 7^3 is the same as 7 x 7 x 7 = 343. I have used x to indicate multiplication but you may often see the asterisk symbol (*) used to mean the same too. So far so good. But the power doesn't need to be a whole number. Your calculator can handle numbers raised to a fractional power too. For example 7^0.5 = 2.6458. Raising a number to the 0.5 is the same as calculating its square root. And this is the same as saying, "What number, when multiplied by itself, equals 7?" Or, to take another example,

100000000^(1/5) = 100000000^0.2 = 39.8107

and this is the same as saying, "What number, when multiplied by itself 5 times, or when raised to the fifth power, is 100000000?" The answer is approximately 39.8107.

Your next query is about AN. Now in normal algebra AN means A multiplied by N. So if A is 3 and N 5, AN is 15. But in alphametics of the sort we are talking about here, AN stands for a two-digit number. It could be 12 or 57 or something similar. But it can't be 11 because a convention is that A and N are different. And it can't be 9 because that would imply that A is zero. Another convention is that we don't allow "leading zeros".

So we are looking for a two-digit number which, when raised to the fifth power, equals EQUATION, an eight-digit number. My example of calculating 100000000^0.2 above is the very calculation modellingman has used in his correct solution. It turns out that the choice for AN is very restricted. In fact there are only 14 candidates, between 26 and 39. Moreover it happens that all the letters of the word EQUATION are different so that restricts the possibities still further. It happens that 38 is the only candidate that, when raised to the fifth power, produces an 8-digit number which has all-different digits, 79235168. Note also that the 4th digit is 3 and the 8th 8. This tallies with A=3 and N=8, i.e. AN=38.

Cinelli

### Who is online

Users browsing this forum: No registered users and 1 guest