Can You Whack The Mole?

Riddler Classic

This week’s Classic is an extension of a puzzle originally by Dan Finkel (and relayed to me by Fawn Nguyen):

In the game of “tax collector,” there are paychecks with different whole number dollar amounts, 1 to N. You choose a paycheck, one at a time. For any check you choose, the tax collector immediately takes any remaining checks (i.e., not already taken by you or the tax collector) whose dollar values are factors of the one you chose. For example, if you choose the $\$10$ check, then the tax collector will immediately take $\$1$, $\$2$ and $\$5$ checks — if any of them is available. Importantly, the tax collector must get something for each paycheck you choose. So if the $\$10$ check is available, but the $\$1$, $\$2$ and $\$5$ checks are not, then you cannot take the $\$10$ check. When there are no more checks you can take, the game is over and all remaining checks go to the tax collector.

In the original version of the puzzle, your goal was to make more money than the tax collector when N was 12 (or 24 or 48). When N was 12, you could make $\$50$ to the tax collector’s $\$28$, meaning you won about 64 percent of the total. When N was 24, you could win about 61 percent of the total, and when N was 48, you could win about 62 percent.

For this puzzle, not only do you want to get more money than the tax collector, you also want to win the biggest possible fraction of the available money. Which value of N (greater than 1) would you choose, so that you can win the greatest fraction of available money?

Solution

Prime numbers have only 1 as another factor. So pick the largest. All other primes will eventually go to the tax collector

You will not have more than half the numbers in your sum.

The value $N$ that will result in the largest proportion of winnings for you will have as many of the top half of values as possible.

Note that 10 is the largest number that has only one prime in its top half, that is, 7.

Answer

$N = 4$ results in the order of $[3,4]$, which yields $\dfrac{3+4}{\sum {4}} = 0.7$

$N = 6$ results in either $[5, 4, 6]$ or $[5, 6, 4]$, which yields $\dfrac{4+5+6}{\sum {6}} \approx 0.71$

$N = 10$ results in some order of $[6, 7, 8, 9, 10]$, which yields $\dfrac{6+7+8+9+10}{\sum {10}} \approx 0.73$

Every other $N > 6$ has at least two primes in its top half, resulting in not a complete top half. $3$ and $5$ are odd and cannot have a complete top half.

I ran some code to confirm results. For each $N$, $3 \le N \le 30$, an order to achieve the maximum sum follows.

Here is the fraction of the total.

Note that the upper limit of the fraction is the sum of the top half of the checks divided by the sum of all checks.

For even $N$,

$$\dfrac{\left(\frac{N}{2}+1 + N\right) \cdot \frac{N}{4}}{(1+N) \cdot \frac{N}{2}}$$

$$=\dfrac{\frac{3N^2+2N}{8}}{\frac{N+N^2}{2}}$$
$$=\dfrac{3N+2}{4N+4}$$

Rohan Lewis

2021.12.27

Code can be found here.