Monday, March 6, 2017

Cryptarithmetic puzzles follow-up

I was asked to write a bit about strategies and answers for the puzzles we gave two weeks ago.

BIG + PIG = YUM
Because the digits in YUM are all distinct from BIG and PIG and there are only 7 letters in this puzzle, we should expect there to be many solutions.

The easiest way to get a feel for the puzzle is to start trying values and see what develops. This was part of the idea of using this puzzle as the opening challenge.

As we play with examples, the kids should notice these things that constrain our possible solutions:

  1. B, G, I, M, P, U, Y must all be distinct
  2. We are adding two three digit numbers and the sum is a three digit number
  3. B, P, and Y are all leading digits
  4. The largest sum possible with two numbers 0 to 9 is 18.
Some conclusions:
(a) G is not 0. If it was, then M would also be 0.
(b) B, P, and Y are all not 0. They are leading digits, the rules of our puzzles say they can't be zero.
(c) G + G is at most 18. It may contribute at most one ten to the calculation of U.  That will only happen if G is 5 or larger.
(d) I + I is at most 18. Along with a potential ten from G+G, that means we have at most 19 coming from the tens. That will only happen if I is 5 or larger.
(e) B+G is at most 9. If there is an extra hundred coming from the tens digits, B+ G is at most 8.
(f) If I is 9, G must be less than 5. Can you see why?
(g) If G is less than 5, I cannot be 0

After these observations, I'd suggest picking values of G, then seeing what values of I are allowed, then checking what remains for B and P. Because we aren't allowed to have duplicates, we quickly see that our choices are constrained.

For example, if G is 1 or 2, then I is at least 3 and we get the following possible solutions (B and P can be interchanged):
431 + 531 = 962
341 + 641 = 982
351 + 451 = 802
371 + 571 = 942
381 + 581 = 962

132 + 732 = 864
132 + 832 = 964
152 + 652 = 804
152 + 752 = 904
182 + 582 = 764
192 + 392 = 584
192 + 592 = 784

There are some more advanced ideas that could come out of trying to count or list all of the solutions, so I'd encourage people to explore. Even this simple puzzle can be a lot of fun!

CAT + HAT = BAD
The A in BAD is the key part of this puzzle. We can get two cases:
(a) A is 0 and T is 1, 2, 3 or 4
(b) A is 9 and T is 5, 6, 7 or 8.

Again, while there are a lot of solutions (and counting them would be a fun challenge) they are easiest to build up by choosing A (either 0 or 9), then T, then seeing what flexibility is left for C and H. Here are some examples:

301 + 401 = 702
301 + 501 = 802
301 + 601 = 902
302 + 502 = 804
302 + 602 = 904
103 + 403 = 506
395 + 495 = 890

SAD + MAD + DAD = SORRY
This was a puzzle without a solution. In this case, it isn't too hard to see that SORRY has too many digits. The best explanation was given by one student:
  • The largest three digit number is 999. 
  • If we add three of them, we will at most get 2997. 
  • SORRY has to be bigger than 10,000.
  • This isn't possible
CURRY + RICE = LUNCH
Unfortunately, this also doesn't have a solution, but the reasoning is more subtle than the previous puzzle.

Here, we can reason as follows:
  • R cannot be 0 because it is the leading digit in RICE
  • Because the tens digit of RICE and LUNCH are both C, R must be 9 and we must have Y + E > 10.
  • This also means R + C + 1 = 10 + C.
  • That will mean the 100s digit of RICE must be the same as the 100s digit of the sum.
  • However, the 100s digit of RICE and LUNCH are different.
Too bad, it was such a cute puzzle!

ALAS + LASS + NO + MORE = CASH
This is the most challenging puzzle from this set.

Some things we notice:
  1. There are ten letters (A C E H L M N O R S) and they must all be distinct.
  2. We are adding three 4-digit numbers and a two digit number to produce another 4 digit number.
  3. A, L, N, M and C are leading digits, so they can't be zeros.
  4. The tens and hundreds digits of CASH (S and A) are also involved in the sums for those digits.
Point 4 has a subtle implication, which I'll illustrate with the hundreds digits. Since L + O must be more than 0, but A is the hundreds digit of the sum, we must have some number of thousands carried over. Because A, L and M are all distinct and larger than 0, the smallest their sum can be is 1+2+3. Putting these two observations together, C must be at least 7.

In this case, I find it helpful to put together a table showing possibilities that we have eliminated:
We can see some more restrictions from the fact that A + L + M must be less than 9. That means we have only the following possible triplets (ignoring order):
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}

One thing we notice is that 1 is in all of these triplets, so either A, L or M must be 1 and none of the other letters can be 1. Another thing we notice is that we don't yet have any way of differentiating A, L, or M, so any ordering of our triplets is possible.  That would mean we have 24 cases to consider.

Let's see how we would work through the cases, starting with A = 1, L = 2, M = 3, the first on our list. Now this, happens to be a stroke of luck, as we'll see.

Starting from the thousands digit, we see that this would make C = 7, if there is a single carry from the hundreds. Indeed, we can see that this must be the value (in the case we are testing), as the carry from there could only come from L + O (plus any carry from the tens digit). Since L is at most 5, L + O is at most 14 and any carry from the tens digit must be less than 6.

Now, in the hundreds digit, we have 2 + O + carry from the tens = 10, so O = 8 - carry from tens.
We know there must be at least one carry from the tens, so O is at most 7. Since 7 is already used by C, let's try 6. That means we need to get 2 hundreds carried over from the tens, so we need
A + N + R + carry from ones = 20, or N + R + carry from ones = 19. Since we have already used 6 and 7, the only way this is possible is if N and R are 8 and 9 (in either order) and we are carrying 2 from the ones.

At this point, the case we've worked through has:
121S + 21SS + 86 + 369E = 71SH

We still have to allocate digits 0, 4, and 5. and we know that S + S + 6 + E = 20 + H. Given our remaining digits, the biggest the left hand can be is if S is 5 and E is 4, making 20. The smallest the right hand can be is if H is 0. Fortunately, this makes the equality hold, so we get our final answer:

1255 + 2155 + 86 + 3694 = 7150

Through the process of checking this case, we learned more about how the carry from lower digits is restricted and it would be faster for us to check through remaining cases.
Let me know how many other solutions you find!

LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL +
LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL +
LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL +
LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL +
LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL +
LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL +
LOL + LOL + LOL + LOL + LOL + LOL LOL + LOL + LOL + LOL + LOL = ROFL

There are 71 LOLs, so this is 71 x LOL = ROFL. While this looks daunting, there are some ideas which take us a long way to the solution.

First, ROFL has 4 digits. If L were 2, 71 x LOL would be more than 14,000, so L must be 1. In fact, ROFL is less than 9861, so LOL is smaller than 9871 / 71 which is 139. We can quickly check
101, 121, and 131 and see that 131 works.

71 x 131 = 9301