Taxman

Description

The game is played between two players on a board consisting of whole numbered tokens labeled 1 through N, where N is any positive whole number.

During each turn, one player (deemed the tax payer) takes a number from the board, and the other player (deemed the taxman) removes all remaining factors of the tax payer's number from the board.

The game ends when there are no legal moves left, and each player's score is calculated by adding up the values of the numbers they have collected. The player with the highest score wins.

Single-player version

In the single-player version, (Taxman, Tax Factor, Number Shark), the human player assumes the role of the tax payer each turn while the computer player is always the taxman.

In addition, the human player may only collect a number that still has proper factors remaining on the board. When there are no legal moves left, the taxman collects all of the remaining tokens on the board.

Two-player versions

In all two-player versions of the game, (The Factor Game, Factor Blast, Factor Blaster, Dr. Factor), the two players swap roles each turn, so that whoever is playing as the taxman during one turn will be the tax payer during the next turn, and vice versa.

In some versions, the tax payer may only collect a number that still has proper factors remaining on the board. If a player picks a number incorrectly, they may or may not lose their next turn, and they may or may not keep the number.

In some versions, the taxman may neglect to collect all of the factors of the tax payer's number, or may attempt to collect a factor incorrectly. The taxman may or may not lose points for missing factors or choosing incorrectly, and the tax payer may or may not be able to steal a factor that the taxman misses.

In some versions, there is the option to remove one or more numbers from the board before the game starts.

Origin and spread

Taxman was invented by Resek sometime in the late 60's or early 70's while working at the Lawrence Hall of Science. It was published as a BASIC program in the September 1973 issue of the People's Computer Company Newsletter, and later appeared in the 1975 programming anthology book What to Do After You Hit Return.

In 1980, Taxman appeared as part of the software collection MECC - Elementary Volume 1 for the Apple II. The concept was later reused in other MECC titles, such as Wonderland Puzzles (as Hedgehog Croquet) and The Secret Island of Dr. Quandary (as Tax Factor) in 1992.

Starting in 1984, Taxman appeared as a coding exercise in a series of programming textbooks written by Lowell Carmony, a professor at Lake Forest College (and Berkeley alumnus). Carmony was part of the writing group for the 1993 NRC publication Measuring Up: Prototypes for Mathematics Assessment, which included Taxman as one of its prototypes. Carmony also described Taxman in an article for SIGCSE.

In 1996, a list of the best possible scores in Taxman, (called the Taxman sequence), was uploaded to the On-Line Encyclopedia of Integer Sequences. As of 2022, the sequence has been calculated out to a board size of 1000.

Around 2000, a version of Taxman was uploaded to the NRW's learn:line educational server under the name Der Zahlenhai (or Number Shark in English). A version of Number Shark was later added to CrypTool in 2006.

In 2015, Taxman appeared in the New York Times' Numberplay column as The Tax Collector.

Two-player versions

A two-player version of Taxman, known simply as The Factor Game, was described in an article for the November 1973 issue of The Arithmetic Teacher, a publication of the National Council of Teachers of Mathematics. The article was later reprinted in the 1975 anthology Games and Puzzles for Elementary and Middle School Mathematics.

In 1983, Factor Blast by Joe DeMuth was published by Hayden Software. Around 2000, educator Terry Kawas developed teaching materials for a similar variant called Factor Blaster which was later uploaded to Mathwire, a math education resource website.

In 1985, Dr. Factor appeared as one of four games in Playing To Learn by Antonia Stone, Joshua Abrams, and Ihor Charischak of HRM Software.

In 1986, another variant, also called The Factor Game, appeared as the first activity in the Factors and Multiples module of the Middle Grades Mathematics Project curriculum, and later appeared as part of the Connected Mathematics Project in 1996. Interactive versions were developed for Macintosh and Windows, and eventually a web version was developed for the NCTM's Illuminations website in 2001.

In education

Taxman and its variants have been studied and used as tools in mathematics and computer science education.

O'Brien used Taxman and another computer game to "foster the development of higher-level thinking skills in children".

Harkin and Martin describe using the two-player version of Taxman, which they called "the factor game", to involve students with concepts of prime and composite numbers, and to apply the fundamental theorem of arithmetic.

Researchers at Michigan State University also used the factor game, together with the Sieve of Eratosthenes, to help improve the quality of arithmetic instruction for middle-school students.

Carmony and Holliday proposed using the one-player game to teach concepts in algorithm design and data structures. They examined the data structures needed to program the Taxman game, and then explored adding intelligence to allow the program to play the game.

Trono describes using the Taxman game as an assignment in a CS2 programming course, dividing the students into teams that each devised a different strategy and competed to find the one that performed best.

Analysis

The winnability, strategy, and optimal score for the single-player version of Taxman have been studied.

First we can make some elementary observations.

Taxman is a zero-sum game, in which the player and the taxman divide a total between them equal to the sum of the numbers from 1 to N, which is N(N+1)/2. To win the game, the player must get a score equal to more than half that sum.

It is easy to see that the best first move is to take the largest prime on the board. Taking it gives the taxman only the number 1, which he will take on the first move anyway, rendering all remaining primes unpickable. Taking the largest prime does not prevent any later picks that could be made, since it has no multiples on the board.

An absolute upper limit to the player's score can be found as follows. Since the taxman must take at least one number on every turn, the best the player can do is to take as many numbers as the taxman, and take them all from the upper half of the range, greater than N/2, leaving the lower half to the taxman. Some simple algebra shows that the sum of these numbers approaches, but is always less than, 3/4 of the total available points. For N=10, the player is able to do this, taking 40 of the available 55 points, or about 73%. For N>10, it is not possible for the player to take all of the numbers above N/2, since some of them inevitably become unpickable as their divisors are taken by the taxman. Because of this, the optimal score for large N is always significantly below this bound. For N ≤ 1000, the average value of the optimal score as a fraction of the available points is found to be about 63%.

Although finding the optimal play for one-player Taxman is probably NP-hard, and therefore prohibitive to compute for large values of N, winning strategies that are efficient to compute have been published.

Hensley, approaching the problem from a number-theory perspective, devised a divide-and-conquer algorithm which he showed wins for large enough values of N. However, he was unable to determine a minimum value of N above which the strategy would always win.