Puzzle Corner

The only paper periodical that is still delivered to my house is MIT’s Technology Review. In the back of every issue, there is a section called Puzzle Corner. As the name implies, it includes puzzles. It’s really an amazing column and has a long history; it has been edited by Allen Gottlieb for more than 50 years. The column consists of densely packed reader-submitted math puzzles and solutions to puzzles published in earlier editions. There are typically three puzzles and the first one almost always focuses on board games (i.e. chess or bridge). While I rarely have the time to solve the puzzles, I seldom miss the chance to read through them.

Earlier this year, the May-April Edition arrived and I immediately flipped to the back to skim through the puzzles. My thirteen year old daughter, Zoe, was sitting beside me on the couch and noticed the chess board graphic in the first problem. She was curious why I had skipped all the content to look at this section. I explained how the column publishes puzzles and how I always read the puzzles but rarely take the time to solve many of them. I told her that many of them required knowledge of either chess or bridge and that I had little interest in chess and had never played bridge. “Oh, here’s one you can solve,” I added as I skimmed the second problem.

Zoe gave me a confused look, “I don’t know how to solve that.” “Sure you do, you could very easily just use your computer to try every option,” I responded. She looked confused, “How?”

And with that, it has become a bit of a pet problem that we’ve continued to discuss over the next few months as I tried to explain to her why I was so certain that this problem could be solved in very little time using a computer. What follows is a bit of a summary of the explanation and the solution that we found.

How?

Working on math puzzles with a middle school student has it's challenges. Having yet to cover probability in school, the concept of a permutation which would easily tell us how many unique ways exist for sorting a set of 9 numbers is not something we can rely on. We have to start more basic.

We’re going to have the computer make guesses for us until it finds a guess that works. For example, we’ll try

to see if that adds up to 1 and we’ll also try

We’ll try all possible ways to arrange those 9 numbers. How many guesses will we need to make?

Let’s change the problem around slightly to make it easier to figure this out. Let’s start with a list of those nine numbers. [1, 2, 3, 4, 5, 6, 7, 8, 9]. Let’s imagine that the first number in the list corresponds to numerator in the first expression, the second number in the list corresponds to the first digit in the denominator, the third item to the second digit in the denominator and so forth. So, for example, [1, 4, 8, 2, 7, 9, 3, 6, 5] would correspond to,

If we want to try all possible guesses, all we have to do is find all the different ways possible to reorder that list of nine numbers. But how does one find all the ways to order a list of nine numbers?

How many ways can we order 9 items?

Let’s start with a smaller problem, just so we can see the pattern more easily. Instead of finding all the ways to order 9 items, let’s first find all the ways to order just 3 items. When we understand that, it should make it much easier to solve the bigger problem with all 9 items.

So we have the list of 3 numbers, [1, 2, 3]. If we were going to take out a piece of paper and just start writing down all the ways to order them, we need to first choose a number for the first item in the list. Why not start with 1?

We’ll eventually do the same thing with the first item being 2 and then 3. But for now, let’s count the number of orderings there are when the first item is 1. Since 1 is accounted for, we now have a list of 2 items, [2, 3]. There are only two ways to order [2, 3]. There is [2, 3] and [3, 2]. So our paper list might start like this,

And then we need to find all the ways to order the list when 2 is the first number.

And finally, we need to find all the ways to order the list when 3 is the first number.

So putting them all together, there are 6 different ways to order the numbers [1, 2, 3].

Notice that when we chose the first item in the list, we had 3 options to choose from [1, 2, 3]. And once we had selected something for the first item, we had 2 things to choose from and there are only 2 ways to order 2 items. So the total number of ways to order a list of 3 items is 3 × 2 = 6. Now, let’s repeat the same thing but let’s find all the ways to order 4 items.

Notice that we have 4 items when we select the first item in the list, then we have 3 items when we select the 2nd item in the list and finally we we have 2 items to choose from. So the number of ways to order 4 items is 4 × 3 × 2 = 24

Let’s just follow the pattern. The number of ways to order the 9 items [1, 2, 3, 4, 5, 6, 7, 8, 9] can be found with,

9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 = 362,880

That seems like a lot but computers are very fast and can make that many guesses in less than a second. We’re also still trying more guesses than we really need to, but this is good enough to solve the problem from the Puzzle Corner in a very short amount of time. Using a simple program that tries all 362,880 guesses and prints out solutions to the problem finds 6 solutions!

It's probably pretty clear by looking at the 6 solutions why our simple program is still trying too many guesses. Addition is communicative, so for example,

Removing the redundant guesses

What follows is not really necessary as we’re obviously able to compute the solution to the problem in a very short amount of time. It’s pretty satisfying, though, to make our program a little bit more efficient and also have it print only one definitive solution to the problem.

The issue is that we found all the unique ways to order the list of 9 numbers, but some of those orderings are actually redundant because what we really want to find is all the unique ways to order those 9 numbers into 3 sets of 3 numbers and the order of those 3 sets does NOT matter. There are a number of ways to eliminate the redundancy, but one way that is pretty easy to integrate into our existing solution is to restrict the order. Let’s only try orderings if the sets of 3 numbers are sorted by their minimum value. So if you consider the example given above,

The minimum value in the first set of 3 is 3, the minimum value in the second set is 6 and the minimum value in the last set is 1. This ordering is not sorted properly since the minimum value in the last set of 3 numbers is smaller than the minimum value in the first set of 3 numbers. This should not be one of our guesses. Consider, however,

This would be considered a valid guess since the minimum of each set of 3 is in sorted order, 1 < 3 < 6. Integrating that into our little program and running it again, this time we get a single solution.

So how many guesses did we have to make now that we’ve eliminated the redundant guesses? A good clue is that previously we got the same answer 6 times and now we only get a single answer. If your guess is 362,880 / 6 = 60,489, then you are correct. The reason is that we have 3 sets where the order doesn’t matter. You can arrange 3 sets in 3 × 2 = 6 different ways. If we then removed all of those orderings, then we reduce the number of guesses by a factor of 6.

Additional Notes

Alan Gottlieb, editor of Puzzle Corner and professor of computer science at NYU, maintains a page about his column that includes the history, ground rules and all the back issues.

When we were trying to figure out how many ways one can re-order a set of 9 numbers, we had to restrict ourselves to middle school math. However, this act of arranging a set of items into an order is known as a permutation. For a set of N items, there are N factorial possible permutations.