# The Tax Collector – The New York Times

This week’s riddle was suggested by Daniel Finkel, a regular contributor to Numberplay and a member of the Seattle-based association. Math for love. We last saw it three weeks ago with Broken Calculator, and this week we’re continuing with something more seasonal. Do we try to –

Tax collector

Tax Collector plays like this: Start with a collection of paychecks, from \$ 1 to \$ 12. You can choose any paycheque to keep. Once you have chosen, the collector receives any remaining paychecks which are factors of the number you have chosen. The collector must receive payment after each move. If you have no movement that gives the collector a salary, then the game is over and the collector receives any remaining salaries.

The goal is to beat the tax collector.

Example:
Round 1: Take \$ 8. The collector receives \$ 1, \$ 2 and \$ 4.
Round 2: Take \$ 12. The collector receives \$ 3 and \$ 6 (other factors have already been taken).

Round 3: Take \$ 10. The collector receives \$ 5.

You’re out of legal moves, so the game is over, and the collector receives \$ 7, \$ 9, and \$ 11, with the remaining paychecks.

Total Notes:
You: \$ 8 + \$ 12 + \$ 10 = \$ 30.
Tax collector: \$ 1 + \$ 2 + \$ 3 + \$ 4 + \$ 5 + \$ 6 + \$ 7 + \$ 9 + \$ 11 = \$ 48.

Questions:

Is it possible to beat the tax collector in this \$ 12 game? If so, how? What is the highest score you can get?

Bonus: What if you played the game with checks from \$ 1 to \$ 24? How about \$ 1 to \$ 48?

We conclude with a little mathematical art: two original tilings by Hamid Naderi Yeganeh, student at Qom University in Iran. Pavings (from Latin tessera, a cube or a square of stone or wood) are tiles using one or more geometric shapes without overlaps or gaps. The art form is a favorite among mathematicians (MC Escher’s Reptiles is a personal favorite) and is very difficult to create. Here are two of Hamid’s recent works:

Below are the shapes Hamid used to create the two pieces above.

I asked Hamid about his interest in tilings and the mechanisms involved in the pairing of South America and Africa. He sent the following response:

I love to create tilings because I think tiling is a powerful art. First of all, I wanted to create a beautiful tessellation. Then I liked to create a good connection between the continents and the mathematical forms.

To make them I started with pencil and paper and then used math to create the exact shapes.

Iranian tiles are a famous art. For example, you can see beautiful tiling work in the Sheikh Lotfollah Mosque.

With that, we end this week’s tax challenges. As always, once you’re able to read the comments for this article, use Gary Hewitt’s Improver to correctly visualize formulas and graphs. (Click here for an introduction.) And send your favorite puzzles to [email protected]

Tax collector solution

Dan here, with this week’s puzzle solution. There are several parts to this one, and while we saw the solutions to several of these parts appear in the comments, it was difficult to come up with a solid argument that each solution is the best it can be. I’ll go through each one separately.

Puzzle # 1: Pay checks from 1 to 12.
Answer: using Joshua Ottthe solution of (which many others also have.)

Yours (the tax collector)
11 (1)
10 (5, 2)
9 (3)
8 (4)
12 (6) – with (7) taken by the collector at the end of the game.

Total: you get 8 + 9 + 10 + 11 + 12 = 50.
The tax collector gets 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Larry gave us the only fully solid proof that I have seen that this solution is optimal.

â€œIt has already been observed that any optimal solution with 12 checks will end up with 7 as an orphan check that will go to taxes.

Consider the 11 checks other than 7. Observe that every time a check is paid, at least one other check goes to taxes (not to mention orphan checks that end up going to taxes). Thus, the number of paychecks is less than or equal to the number of fiscal checks, or even less, since there is an odd number, 11, of checks considered.

Now consider 11 distinct numbers, to be divided into sets A and B such that the size of A is less than the size of B and the difference between the sums of the numbers of A and B is maximum. Obviously the only way to do this is to put the 5 largest numbers in A and the remaining numbers in B: A = {12,11,10,9,8}. It has already been shown that {12, 11, 10, 9, 8}, in a certain order, is a solution to our problem, and we have just shown that {12, 11, 10, 9, 8} is the single maximum solution to the problem.

A very nice argument!

We haven’t seen anything so tidy for future puzzles, but try to use the same idea.

Puzzle # 2: Paycheques from 1 to 24.

This solution is due to Joshua Ott:

Yours (the tax collector)
23 (1)
9 (3)
21 (7)
15 (5)
14 (2)
22 (11)
20 (10, 4)
18 (9)
16 (8)
24 (12) – with (13, 17 and 19) left on the table.

Totals: You get 9 + 14 + 15 + 16 + 18 + 20 + 21 + 22 + 23 + 24 = 182
The tax collector gets 118.

Is it optimal? We can prove that this is the case, by extending the evidence from above.

You can get only one prime number, so you might as well take 23. After that, prime numbers greater than 12 will be “orphan”, so we can now give them to the tax collector. It’s 13, 17, and 19. That leaves 19 checks. The collector gets at least half of the remaining checks, or 10 extra checks, so we get at most 9 extra checks, for a total of 10. This is the same as the total number of checks in our solution above.

Is our solution optimal? Checks 14-24 are the most we could possibly have. All we have to prove is that 9 is the best option left. The only non-prime numbers greater than 9 are 10 and 12. Is either of these checks possible to get? Not without sacrifices. Write down the factors of 12, 16, and 24, and you will see that you can take at most two of these numbers. Whichever pair you take, you’ve eliminated all factors from the third, so the tax collector is sure to get it. If you take 12, the collector gets 16 or 24, that’s a bad trade. Better to take 9 and 16 than 12 and a smaller number.

Likewise, if you choose three paychecks from the group of {10, 15, 21, 14}, you will have eliminated all factors from the fourth and will have to give it to the tax collector. In other words, if you take 10, you will have to give up 14, 15 or 21. Another bad trade. Therefore, 9 is the best option for the final check, and \$ 182 is the most you can get with those 24 paychecks.

Puzzle n Â° 3: Pay checks from 1 to 48.

Jeremy Weissman gave us this method to get \$ 734:

47 (1)
25 (5)
35 (7)
21 (3)
39 (13)
33 (11)
26 (2)
46 (23)
38 (19)
34 (17)
27 (9)
45 (15)
18 (6)
42 (14)
30 (10)
28 (4)
44 (22)
36 (12)
40 (8.20)
32 (16)
48 (24)

How does it stack up? Using our same method, we know you should take 47, lose 1, and give up hope on 29, 31, 37, 41, and 43. That leaves 41 paychecks remaining, of which you will get at most 20. So we I looking for a solution, hopefully with 21 paychecks in total, as many as possible above 24. JeremyThe solution of includes all non-prime numbers greater than 24, which is excellent; these do not require any justification. The only numbers that we have to justify are 18 and 21. Could these have been exchanged for 20, 22 or 24, without paying too high a price?

The answer is no, and we can prove it by finding sets of paychecks that we can’t all have. I’m claiming you can’t have all the numbers in any of these sets:
{24, 32, 48}
{22, 26, 33, 39}
{20, 21, 25, 26, 27, 28, 30, 35, 39, 42, 45}

You can verify that this is correct by writing down all the factors. This means that choosing 20, 22, or 24 would cost you a larger number, a cost high enough that the potential benefit isn’t worth it.

So \$ 734 is indeed the maximum you can get with paychecks of 1-48.

And an excellent writing of this argument has appeared from ShnÃ©or Friday morning. See comments for these details.

General.

Some very interesting ideas on how to approach this problem in general, from LANthe idea of â€‹â€‹building a graph for Markstrategy of getting 43% of the take by making certain strategic choices that still work. I would like to share Ricardo Echstrategy, whose idea of â€‹â€‹Mark exceeds the 50% mark:

â€œThe idea is to show that we can always choose payments in N / 5 +1 to N that total more than half of the sum, using only multiples of 2, 3 and 5.

For the numbers between N / 25 + 1 and N / 5, pay them to the tax authorities by selecting 5 times these numbers …

Now for the numbers in the range N / 5 + 1 to N / 3 which are not divisible by 5, pay them to the tax authorities by selecting the latter 3 times …

Finally, for the numbers in the range N / 3 + 1 to N / 2 which are not divisible by 3 or 5, pay them to the tax authorities by selecting them twice.

Check out Ricardo Ech’s comments to see the algebra and estimates that sketch a proof that this strategy actually works for any N large / good enough. A very nice method in play here.

This concludes this week’s puzzle in a most satisfying way! It always seems like there is a way to walk away with more money than the tax collector, except for odd little cases like 1 or 3 paychecks. Thank you all for your contribution – it was a really fun discussion and problem to be a part of. Till next time.

Gary here, wrapping it up. Thanks, Dan, for the great puzzle and recap. And thank you also to everyone (including many newcomers) who contributed this week: Abigail, Alan W, Aldrin, Anita, Anjali, Evan, Hans, Jae, Jeremy Weissmann, John K, Jonathan, Joshua Ott, LG, LAN , Larry, Lauren, Lissy, Mark, mwithit, Ravi, Ricardo Ech, Seth Cohen, Shneor, sj, Stuart Wells, Tim and Tom.