Skip to content

Best score in the divisor tax game on 1 to 10

Question

The numbers 11 through 1010 are written on a board. On each turn you claim one remaining number, and a tax collector immediately removes every remaining number that divides it (other than itself). You may only claim a number if at least one of its proper divisors is still on the board. When no legal move exists, the collector takes whatever is left. Your score is the sum of what you claimed. What is the highest score you can guarantee?

Short answer

4040. Only one prime can ever be claimed (all primes lose their only proper divisor 11 at once), so take 77 first. Then claim 99 (losing 33), 66 (losing 22), and then 88 and 1010 (losing 44 and 55): you hold 6+7+8+9+10=406+7+8+9+10=40, and an exhaustive search confirms nothing better is possible.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question