# When is the “Taxman Game” winnable?

I recently came across the "Taxman Game" the rules are in the link, but I'll repeat them here:

We start with a pile of integers, from 1 to some number that you choose [$n$]. You take one, and I get all the others that divide it evenly. We repeat until there's nothing left. BUT (big but!) I have to get something on each turn. So when none of the numbers in the list have any divisors that have not been taken, I take them all. Your score is the sum of all the numbers you took, while my score is the sum of all the numbers I took.

The 'you' and 'I' is a bit confusing, there is only one player here - the 'you' - as the 'taxman' ('I') side is entirely deterministic.

The question I have is this: for what $n$ is the game winnable? I think that it is winnable for all $n>3$ but I'm not sure how to go about proving this. At $n=3$, the best strategy is a draw (pick 3, taxman get 1 and 2), while for $n=1$, the player has no winning move so the lowest bound on winnable $n$ must be $n>3$ but is there a higher $n$ that is unwinnable?

I'd also be interested in whether there is a 'best' strategy guaranteed to give a win where it is possible and the largest possible winning margin when doing so.

• $1$ divides $3$ evenly, doesn't it? Also, for $n=2$ and $n=1$, the first player wins by taking the number $n$. So I'm confused here $-$ when you say "winnable", I assume that you mean winnable by the first player; but then the game seems to be winnable for $n=1,2,3$. – TonyK Jun 25 '15 at 11:29
• If you take 3 why would the taxmen get 2? 2 doesn't divide 3 evenly. – Amy B Jun 25 '15 at 12:19
• @TonyK: Winnable as in the player score is higher than the Taxman's. For 3, if you pick 3 then the Taxman gets 1 as a divisor but that leaves 2 and you can't pick 2 as it has no remaining divisor. Thus you and the Taxman both get a score of 3 for a draw not a win. – Jack Aidley Jun 25 '15 at 12:20
• @AmyB: because at the end of the game the Taxman gets any numbers that have no remaining divisors and after you've picked 3 there are no divisors of 2 left so it goes to the Taxman. – Jack Aidley Jun 25 '15 at 12:21
• You should add what you just said to the question (that at the end the Taxman gets any numbers that have no remaining divisors). Otherwise this game is exactly like the factor game (illuminations.nctm.org/Activity.aspx?id=4134) that my students play. Our strategy is to always pick the largest prime number on the first turn. – Amy B Jun 25 '15 at 12:24

Some observations on the game:

• The $1$ will always go to P2 on turn 1
• $P1$ can pick only one of the primes, so should pick the largest on turn 1 (by the Bertrand-Chebyshev theorem we know that for $n \ge 4$ there is always a prime exceeding $n/2$, so the largest prime $\le n$ has no multiples in $\{1,2,3,...,n\}$)
• all other primes will go to $P2$
• picking a power of $2,3,5,...$ will result in the elimination of all lower powers of $2,3,5,...$
• it never makes sense to pick the second largest power of $2$
• if the only selectable numbers left are powers of a prime $p$, it is best to pick in alternating powers of $p$ ending at the highest power, for example, choosing $4,16,64$ for $p=2, 64 \le n < 128$
• if $n = p$ where $p \ge 5$ is prime, there is a largest prime $q \in \{1,2,3,...,p-1\}$ such that $\dfrac{p+1}{2} < q < p$. Then if P1's best score differential for $n=p-1$ is $S(p-1)$ we have $S(p) = S(p-1) + p - 2q$ (since the only action P1 should change is his choice of largest prime) and also $S(p-1) - p < S(p) < S(p-1) - 1$
• if $n$ is not prime, then $S(n) = S(n-1) - n$ unless P1 chooses $n$ at some point in the game. If P1 can obtain a better score by choosing $n$ he should; otherwise, he should not.

Robert Moniot's "greedy heuristic" seems like a good candidate for a winning strategy. He computed the optimal strategy for all n up to 49, but he did not find a simple rule to describe it for arbitrary n.

There's an interesting discussion thread on /r/mathriddles about the taxman game. No proofs of optimality, but I thought I'd share the link since there's a number of suggested strategies on there.