Legal 21 (Teacher’s Corner Version)

Here’s the problem again: Young Saul, a budding mathematician and printer, is making himself a fake ID. He needs it to say he’s 21. The problem is he’s not using a computer, but rather he has some symbols he’s bought from the store, and that’s it. He has one 1, one 5, one 6, one 7, and an unlimited supply of + – * / (the operations addition, subtraction, multiplication and division). Using each number exactly once (but you can use any number of +, any number of -, …) how can he get 21 from 1, 5, 6, 7? Note: you can’t do things like 15+6 = 21. You have to use the four operations as ‘binary’ operations: ((1+5)*6)+7.

Thoughts on the solution. With a problem like this, my first thought is to just try a few combinations and see if I get lucky. After a few minutes of fruitless searching, however, you realize you need to be more clever.

First idea: Think about the number 21. How can we get it? Well, one possibility is to look at its factorizations. We have 21 = 1 * 21, or 3*7. While we do have a 7, there doesn’t seem to be a way to get 3 from the remaining three numbers (1, 5 and 6). We can get 2 (1+6-5), but 3 seems to elude us. If we try to think about divisions there are so many possibilities it gets hopeless, and similarly with additions and subtractions. This suggests that we need another idea.

Second idea: Let’s try and get a sense of how many possible solutions there are. Are there a lot of candidates to check, or a small amount? There are only 4 numbers. As each binary operation involves two numbers, we can only have three binary operations. We do have to worry about how to group things (parentheses and order), but it does seem like the number of possible combinations is finite. As a rough upper bound, maybe there are 4^3 = 64 choices for the three binary operations, and maybe 4! = 24 ways to order the four numbers to be fed in, for a very finite number of options (4^3 * 4! = 1536 possibilities.

A little thought, however, reveals that this might be a bit off. We have to worry about how the binary operations are grouped. For example, if the three binary operations are +, – and * (in that order), then ((5+6) – 1) * 7 is different than 5+((6-1)*7). So perhaps the answer is a bit more than 1536, but probably not enormously bigger.

The upshot of all of this is that the number of candidates to check is more th an 1500 but probably less than 15,000. This suggests that it’s unlikely we’ll find the answer by brute force searching; there are probably too many possibilities, and if the answer were easily found it probably wouldn’t be posted as a riddle! (Of course, this suggests you should try the less obvious candidates, but by definition these are harder to think of and are easily missed). The other takeaway is that this problem is ideally suited for a computer. There’s a large number of possibilities to check for a person, but not for a computer. If there were 10^12 candidates it would be a different story, but if we can find an intelligent way to go through the candidate space, a computer should find the solution.

Third idea: We thus need to find a good way to enumerate all possible candidates. This is the challenge, designing a program go through all possible ways to combine the four numbers without missing any possibilities. Thus, not only do you need to loop through the 4! arrangements of the numbers, you need to loop through the binary operations!

If you remember diagramming sentences in an English class, that’s what we need to do here. THe difference is we need to find all the different (mathematical) sentence structures for combining four numbers with three binary operations. It turns out that there are just 5 basic types of sentences. Let A(x,y), B(x,y), and C(x,y) represent arbitrary binary operations applied to two numbers. Thus each of these represents either x+y, x-y, x*y, or x/y.

Arrange the numbers in some order, say w, x, y, z. There are 4! = 24 ways to arrange the numbers where order counts. We do have to be careful, as order matters for two of the four binary operations (note x-y and x/y are not equal to y-x and y/x).

We now have to enumerate all the different sentence types. For example, one possibility is

C( A(w,x), B(y,z) ).

This means do a binary operation on w,x; a binary operation on y,z; then a binary operation on the two results. This can range from

(w+x) + (y+z)

to

(w/x) / (y/z),

depending on our choices of A, B and C.

Another sentence is

C( B(A(w,x), y), z).

This can range from

((w+x)+y) + z

to

((w/x)/y) / z,

with all stuff in between, such as

((w-x)/y) + z.

There are three other “sentence” types. Collecting all five, we find the possible sentence strutures are

(1) C(A(w,x), B(y,z) ). Example: (w+x) + (y+z).

(2) C(B(A(w,x), y), z). Example: ((w+x)+y) + z.

(3) C(z, B(y, A(w,x))). Example: z + (y + (w+x)).

(4) C(B(y, A(w,x)), z). Example: (y + (w+x)) + z.

(5) C(z, B(A(w,x), y)). Example: z + ((w+x) + y).

The hardest part is making sure you don’t miss any sentence structures. For me, I found it very helpful to think about adding four numbers and all the different ways I could group it (hence the examples listed above).

We now loop through all 4!=24 ways of assigning 1,5,6,7 to w,x,y,z, and weloop through all ways of assigning binary operations to A, B and C (there are 4^3 = 64 ways to do this).

Note that for some sentences, different assignments lead to the same output. For example, if all the binary operations are addition than all 4! = 24 arrangements of the four numbers lead to the same output. As this is such a straightforward program to write and run, it’s faster to just write simple code and execute it then to spend a lot of time telling the computer not to do certain calculations that give the same output as other cases. In programming, it’s often good advice to not worry about being too clever unless you run into issues with how fast the code runs.

Thus, there are 5 * 4^3 * 4! = 7680 candidates. While this is too large for most humans to do by hand, a computer can output the result of checking all of these almost instantaneously.

The solution turns out to involve two divisions, which might explain why most people are unable to find it. The answer is 6 / ((1 – (5/7)). This gives us 21 from 42/2, and is of the sentence (3) type.

General comments: There are numerous riddles in the world. Why this one? What I like about this problem is that it’s all about finding an efficient way to enumerate possibilities. How do we intelligently search the space of possible solutions? This is one of the biggest problems in mathematics and computer science. It is often very useful to break a hard problem into cases; however, it is a real challenge to make sure your cases exhaust all possibilities. The hardest part here is figuring out all the different sentence structures.