A Beautiful Puzzle

Occupy Math spent his last post railing against a lack of support for K-12 teachers trying to teach fractions. This week he turns to a wonderful puzzle that can serve as a discovery learning exercise for some of the skills needed to work with fractions. This puzzle is called the Taxman Puzzle or taxman problem and Occupy Math learned about it at the Canadian Math Education Study Group. The colleague that contributed the problem to the working group on problem solving called it a unicorn problem. It is easy to explain, teaches valuable concepts, permits incremental progress, and is open-ended.

Unicorn problems are problems that engage and instruct in a smooth, natural fashion.

The taxman problem for the number 12 is posed as follows. The puzzle starts with 12 checks for $1, $2, $3, … through $12. The image above can be used as a worksheet for the problem. The player chooses a check and then the taxman gets all checks with amounts that evenly divide the amount of the check the human chose. There is one important constraint – the player may not take a check unless there is at least one for the taxman to take. This means if the player takes 7, the taxman takes 1, but then the player can never take 11 because none of the remaining checks have amounts that divide 11 evenly. The taxman has no strategy – he is purely reactive. The player’s goal is to maximize the amount of money he keeps. Notice that it is possible to leave checks on the table that no-one gets (in fact, this is inevitable for most versions of the problem). Partial spoiler: you cannot get more than $50 for the 12-check version of the Taxman Puzzle (you still need to find the sequence of checks taken that permits this).

Dan Hoey’s notes on the taxman problem tell us that:

The Taxman game was invented by Diane Resek, a mathematician at San Francisco State University, some time in 1971-1973. She made it up as an teaching aid to motivate schoolchildren to practice arithmetic. The game was distributed for the Apple II by the Minnesota Educational Computing Corporation. It has also been distributed under the titles “Dr Factor”, “Factor Blaster”, and “Number Shark” (“Zahlenhai” in German). There is also an unrelated arcade-style game named Taxman that was popular on the Apple II.

Doing well on this puzzle requires that students think, and think hard, about divisors and factors

Occupy Math solved the cases from 1-20 by hand (and proved he had the correct answer – which is trickier) and then got frustrated and wrote a program that solves the problem. In fact Occupy Math wrote the program five times, speeding up the code with each revision. A simple program asks the computer to just check all the possibilities, but it takes a completely absurd amount of time to solve the version of the problem where the largest check is $35. Occupy Math won’t go into the details of the programming tricks he used, but this problem is a marvelous one for teaching heuristic programming. (A (good) heuristic is a rule of thumb that often helps.) The one known, absolutely reliable heuristic for the taxman problem is to take the largest available prime number first.

The heuristics Occupy Math used on the taxman problem had to do with the order in which his exhaustive search tried checks – the ones that would give the taxman the fewest checks (preferably only one) were tried first. In addition, the code kept track of the best answer found so far and abandoned partial solutions that could never beat the current best known solution. This is an incredibly useful programming trick called branch-and-bound. Sadly, it is not too useful for humans with pencil-and-paper because it requires you to remember way too many details.

Once Occupy Math had the first 35 solutions to the problem, he was able to find the first 158 answers on the internet – as well as Dan Hoey’s notes and other articles and information on the taxman problem. In German, for example, the quote above from the notes tells us the problem is called the number shark problem. Another search term!

How on earth do you look up a list of numbers that solve a problem on the internet? Efficiently?

Occupy Math is about to reveal a very useful tool – a Secret of the Guild, as it were, for mathematicians. The Online Encyclopedia of Integer Sequences currently indexes just over 274,000 sequences – like the sequence of answers to the taxman problem – and it is growing all the time.

Interested in the number of ways to fill a path as wide as the long dimension of one brick with bricks, based on its total length? Solve the first few examples (shown above) and get the answers 1,2,3,5,8. Type “1,2,3,5,8” into the OEIS search window and get this. You can also search for sequences by their name or the name of the problem they solve (e.g.: “taxman sequence”). The encyclopedia was founded in 1964 – as a paper book. It’s actually much older than the internet. Occupy Math has used the book version – give thanks that you can use a search interface.

What use is the OEIS in education?

There are at least a couple of uses. If a bright student comes to you having found a pattern of numbers, the OEIS is fairly likely to know about it. It is written in a mixture of colloquial English and high mathematics – but Occupy Math would be happy to help if you get stuck. Similarly, if you are constructing a puzzle for your students, the answer to which is a sequence of answers to “how many” questions, you can solve the first few (three to ten) cases and get the rest of the pattern from the encyclopedia. If you find something new, there is even a form to let you contribute your sequence.

The taxman problem is an excellent puzzle, it is a good pre-practice for fractions, and it is a wonderful problem for teaching heuristic programming. Here’s a way to use this as an in-class exercise. Start the students with the version where the largest check is $12. As students are working put the “best so far” results on the board – that’s what we did in the problem solving session at the conference. If a bright student solves the $12 version, ask them to do the $18 version. The colleague that introduced this problem at the CMESG conference did this to the group I was working with after we solved the maximum $12 version.

Today’s Occupy Math went a little deeper into the ocean of math that usual – but the taxman problem and the OEIS are both too cool to keep under his hat. Occupy Math is starting a project to generate resources for teachers. This post is the first in a new category called for teachers. Given that Occupy Math prefers to be reader-driven, please comment or tweet requests for the type of things you might like to see developed!

I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s