The Puzzle Noob’s New Game

Question

This is a generalized version of a TED-ED puzzle.

You just wrote a very good puzzle on PSE, getting three upvotes a week. However, the puzzle noob hates your puzzles, and sends you to their dimension of “bad” puzzles.

When you reach the dimension, the noob lays some number $n$ of boxes (where $10 \le n \le 100$) on the ground, where each box has coins in it: one box has $1$, another has $2$, and so on up through $n$. Each box is labelled with the number of coins it contains. Each round, you take one of the boxes, and the noob takes every box which divides it. For example, if you take the box with $12$ coins, boxes $1$, $2$, $3$, $4$ and $6$ all go to the noob. You can only take boxes with at least one other untaken box dividing it. For example, if the only boxes left are $3$, $9$ and $97$, you cannot take the $97$.

When you run out of moves, the noob takes every untaken box. And if your boxes have more coins altogether than the noob’s, you win and get to go home, then write and solve more puzzles. If not, you will lose stuck in the dimension forever, which apparently has no access to PSE.

Question: for which values of $n$ do you have a winning strategy, and what are the strategies for varying values of $n$ (partial answers welcome)?

Answer 1

COMPLETE ANSWER

Winning strategies are possible for

All $n$ up to $1000$, and likely well beyond that.

In each round, choose the largest number with a single divisor among the remaining boxes. (For all tested $n$, this was always possible until there were no legal moves.)

Results for $n$ up to $100$ using this strategy are shown at the end of this answer.

For small values of $n$, it is easy to find winning sequences. One thing to note is that you can only ever take one prime number, and it must be taken first. For $n=10$ you have the optimal cache with

7, 9, 6, 10, 8
For a total of 40 coins, leaving the noob with just 15 coins:
1, 3, 2, 5, 4

I found solutions for $n$ up to $15$ on paper before running a greedy algorithm via code. Here are some optimal solutions for $n$ up to $20$.

n=11 Player score: 44 Noob score: 22
P{11 9 6 10 8} N{1 3 2 5 4 7}

n=12 Player score: 50 Noob score: 28
P{11 10 9 8 12} N{1 2 5 3 4 6 7}

n=13 Player score: 52 Noob score: 39
P{13 10 9 8 12} N{1 2 5 3 4 6 7 11}

n=14 Player score: 66 Noob score: 39
P{13 14 10 9 8 12} N{1 2 7 5 3 4 6 11}

n=15 Player score: 81 Noob score: 39
P{13 9 15 10 14 8 12} N{1 3 5 2 7 4 6 11}

n=16 Player score: 89 Noob score: 47
P{13 9 15 10 16 14 12} N{1 3 5 2 4 8 7 6 11}

n=17 Player score: 93 Noob score: 60
P{17 9 15 10 16 14 12} N{1 3 5 2 4 8 7 6 11 13}

n=18 Player score: 111 Noob score: 60
P{17 9 15 10 18 14 12 16} N{1 3 5 2 6 7 4 8 11 13}

n=19 Player score: 113 Noob score: 77
P{19 9 15 10 18 14 12 16} N{1 3 5 2 6 7 4 8 11 13 17}

n=20 Player score: 124 Noob score: 86
P{19 15 10 20 16 14 12 18} N{1 3 5 2 4 8 7 6 9 11 13 17}

Using the strategy presented in the first spoiler, we obtain these results:

 10 [40 : 15]  7 9 6 10 8
 11 [44 : 22]  11 9 6 10 8
 12 [48 : 30]  11 9 6 12 10
 13 [50 : 41]  13 9 6 12 10
 14 [64 : 41]  13 9 6 14 12 10
 15 [81 : 39]  13 9 15 10 14 8 12
 16 [81 : 55]  13 9 15 10 14 8 12
 17 [85 : 68]  17 9 15 10 14 8 12
 18 [111 : 60]  17 9 15 10 18 14 12 16
 19 [113 : 77]  19 9 15 10 18 14 12 16
 20 [121 : 89]  19 9 15 10 20 18 16 14
 21 [144 : 87]  19 9 21 15 14 18 12 20 16
 22 [166 : 87]  19 9 21 15 14 22 18 12 20 16
 23 [170 : 106]  23 9 21 15 14 22 18 12 20 16
 24 [178 : 122]  23 9 21 15 14 22 18 12 24 20
 25 [178 : 147]  23 25 15 21 14 22 8 20 12 18
 26 [204 : 147]  23 25 15 21 14 26 22 8 20 12 18
 27 [247 : 131]  23 25 15 27 21 14 26 22 18 12 24 20
 28 [279 : 127]  23 25 15 27 21 14 28 26 22 20 18 16 24
 29 [285 : 150]  29 25 15 27 21 14 28 26 22 20 18 16 24
 30 [297 : 168]  29 25 15 27 21 14 28 26 22 20 30 16 24
 31 [299 : 197]  31 25 15 27 21 14 28 26 22 20 30 16 24
 32 [299 : 229]  31 25 15 27 21 14 28 26 22 20 30 16 24
 33 [336 : 225]  31 25 15 33 27 22 26 21 18 30 20 28 16 24
 34 [370 : 225]  31 25 15 33 27 22 34 26 21 18 30 20 28 16 24
 35 [418 : 212]  31 25 35 21 33 27 22 34 26 18 12 28 24 32 20 30
 36 [418 : 248]  31 25 35 21 33 27 22 34 26 18 12 28 24 32 20 30
 37 [424 : 279]  37 25 35 21 33 27 22 34 26 18 12 28 24 32 20 30
 38 [462 : 279]  37 25 35 21 33 27 22 38 34 26 18 12 28 24 32 20 30
 39 [479 : 301]  37 25 35 21 39 33 27 26 38 34 18 12 28 24 32 20 30
 40 [479 : 341]  37 25 35 21 39 33 27 26 38 34 18 12 28 24 32 20 30
 41 [483 : 378]  41 25 35 21 39 33 27 26 38 34 18 12 28 24 32 20 30
 42 [549 : 354]  41 25 35 21 39 33 27 26 38 34 18 42 28 36 24 32 20 30
 43 [551 : 395]  43 25 35 21 39 33 27 26 38 34 18 42 28 36 24 32 20 30
 44 [595 : 395]  43 25 35 21 39 33 27 26 38 34 18 42 28 44 36 24 32 20 30
 45 [660 : 375]  43 25 35 21 39 33 27 45 26 38 34 18 42 30 28 44 36 24 40 32
 46 [706 : 375]  43 25 35 21 39 33 27 45 26 46 38 34 18 42 30 28 44 36 24 40 32
 47 [710 : 418]  47 25 35 21 39 33 27 45 26 46 38 34 18 42 30 28 44 36 24 40 32
 48 [726 : 450]  47 25 35 21 39 33 27 45 26 46 38 34 18 42 30 28 44 36 24 48 40
 49 [750 : 475]  47 49 35 21 39 33 27 45 26 46 38 34 18 42 30 28 44 36 24 48 40
 50 [800 : 475]  47 49 35 21 39 33 27 45 26 46 38 34 18 42 30 50 28 44 36 24 48 40
 51 [825 : 501]  47 49 35 21 51 39 34 46 38 33 27 45 18 42 30 50 28 44 36 24 48 40
 52 [877 : 501]  47 49 35 21 51 39 34 46 38 33 27 45 18 42 30 50 28 52 44 36 24 48 40
 53 [883 : 548]  53 49 35 21 51 39 34 46 38 33 27 45 18 42 30 50 28 52 44 36 24 48 40
 54 [883 : 602]  53 49 35 21 51 39 34 46 38 33 27 45 18 42 30 50 28 52 44 36 24 48 40
 55 [945 : 595]  53 49 35 55 33 51 39 34 46 38 27 45 18 30 50 20 52 44 40 36 32 48 28 42
 56 [945 : 651]  53 49 35 55 33 51 39 34 46 38 27 45 18 30 50 20 52 44 40 36 32 48 28 42
 57 [968 : 685]  53 49 35 55 33 57 51 39 38 46 27 45 18 30 50 20 52 44 40 36 32 48 28 42
 58 [1026 : 685]  53 49 35 55 33 57 51 39 38 58 46 27 45 18 30 50 20 52 44 40 36 32 48 28 42
 59 [1032 : 738]  59 49 35 55 33 57 51 39 38 58 46 27 45 18 30 50 20 52 44 40 36 32 48 28 42
 60 [1056 : 774]  59 49 35 55 33 57 51 39 38 58 46 27 45 18 30 50 20 60 52 44 40 32 48 28 42
 61 [1058 : 833]  61 49 35 55 33 57 51 39 38 58 46 27 45 18 30 50 20 60 52 44 40 32 48 28 42
 62 [1120 : 833]  61 49 35 55 33 57 51 39 38 62 58 46 27 45 18 30 50 20 60 52 44 40 32 48 28 42
 63 [1219 : 797]  61 49 35 55 33 57 51 39 38 62 58 46 27 63 45 18 42 30 50 28 56 52 44 40 60 32 48
 64 [1219 : 861]  61 49 35 55 33 57 51 39 38 62 58 46 27 63 45 18 42 30 50 28 56 52 44 40 60 32 48
 65 [1251 : 894]  61 49 35 65 55 39 57 51 38 62 58 46 27 63 45 18 42 30 50 28 56 52 44 40 60 32 48
 66 [1317 : 894]  61 49 35 65 55 39 57 51 38 62 58 46 27 63 45 18 42 30 50 28 56 52 44 66 40 60 32 48
 67 [1323 : 955]  67 49 35 65 55 39 57 51 38 62 58 46 27 63 45 18 42 30 50 28 56 52 44 66 40 60 32 48
 68 [1391 : 955]  67 49 35 65 55 39 57 51 38 62 58 46 27 63 45 18 42 30 50 28 68 56 52 44 66 40 60 32 48
 69 [1422 : 993]  67 49 35 65 55 39 69 57 51 46 62 58 27 63 45 18 42 30 50 28 68 56 52 44 66 40 60 32 48
 70 [1498 : 987]  67 49 35 65 55 39 69 57 51 46 62 58 27 63 45 18 42 70 50 28 68 56 52 44 66 40 36 60 32 48
 71 [1502 : 1054]  71 49 35 65 55 39 69 57 51 46 62 58 27 63 45 18 42 70 50 28 68 56 52 44 66 40 36 60 32 48
 72 [1606 : 1022]  71 49 35 65 55 39 69 57 51 46 62 58 27 63 45 18 42 70 50 28 68 56 52 44 66 40 36 72 60 48 64
 73 [1608 : 1093]  73 49 35 65 55 39 69 57 51 46 62 58 27 63 45 18 42 70 50 28 68 56 52 44 66 40 36 72 60 48 64
 74 [1682 : 1093]  73 49 35 65 55 39 69 57 51 46 74 62 58 27 63 45 18 42 70 50 28 68 56 52 44 66 40 36 72 60 48 64
 75 [1793 : 1057]  73 49 35 65 55 39 69 57 51 46 74 62 58 27 63 45 75 50 70 42 54 28 68 56 52 44 66 40 36 72 60 48 64
 76 [1869 : 1057]  73 49 35 65 55 39 69 57 51 46 74 62 58 27 63 45 75 50 70 42 54 28 76 68 56 52 44 66 40 36 72 60 48 64
 77 [1873 : 1130]  73 49 77 55 65 39 69 57 51 46 74 62 58 27 63 45 75 50 30 54 42 70 28 76 68 56 52 44 66 40 60 32 48 72
 78 [1991 : 1090]  73 49 77 55 65 39 69 57 51 46 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 60 40 72 56 48 64
 79 [1997 : 1163]  79 49 77 55 65 39 69 57 51 46 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 60 40 72 56 48 64
 80 [2029 : 1211]  79 49 77 55 65 39 69 57 51 46 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 60 40 80 72 64 56
 81 [2029 : 1292]  79 49 77 55 65 39 69 57 51 46 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 60 40 80 72 64 56
 82 [2111 : 1292]  79 49 77 55 65 39 69 57 51 46 82 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 60 40 80 72 64 56
 83 [2115 : 1371]  83 49 77 55 65 39 69 57 51 46 82 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 60 40 80 72 64 56
 84 [2207 : 1363]  83 49 77 55 65 39 69 57 51 46 82 74 62 58 27 63 45 75 50 30 78 54 52 76 68 44 66 42 70 36 84 60 56 72 48 80 64
 85 [2213 : 1442]  83 49 77 55 85 65 51 69 57 46 82 74 62 58 27 63 45 75 50 30 54 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 86 [2299 : 1442]  83 49 77 55 85 65 51 69 57 46 86 82 74 62 58 27 63 45 75 50 30 54 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 87 [2340 : 1488]  83 49 77 55 85 65 51 87 69 58 86 82 74 62 57 27 63 45 75 50 30 54 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 88 [2340 : 1576]  83 49 77 55 85 65 51 87 69 58 86 82 74 62 57 27 63 45 75 50 30 54 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 89 [2346 : 1659]  89 49 77 55 85 65 51 87 69 58 86 82 74 62 57 27 63 45 75 50 30 54 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 90 [2382 : 1713]  89 49 77 55 85 65 51 87 69 58 86 82 74 62 57 27 63 45 75 50 30 90 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 91 [2418 : 1768]  89 49 91 77 65 85 51 87 69 58 86 82 74 62 57 27 63 45 75 50 30 90 42 70 28 84 76 68 60 56 52 78 44 66 32 80 48 72
 92 [2510 : 1768]  89 49 91 77 65 85 51 87 69 58 86 82 74 62 57 27 63 45 75 50 30 90 42 70 28 92 84 76 68 60 56 52 78 44 66 32 80 48 72
 93 [2545 : 1826]  89 49 91 77 65 85 51 93 87 69 62 86 82 74 57 27 63 45 75 50 30 90 42 70 28 92 84 76 68 60 56 52 78 44 66 32 80 48 72
 94 [2639 : 1826]  89 49 91 77 65 85 51 93 87 69 62 94 86 82 74 57 27 63 45 75 50 30 90 42 70 28 92 84 76 68 60 56 52 78 44 66 32 80 48 72
 95 [2683 : 1877]  89 49 91 77 65 95 85 57 93 87 69 62 94 86 82 74 27 63 45 75 50 30 90 42 70 28 92 84 76 68 60 56 52 78 44 66 32 80 48 72
 96 [2683 : 1973]  89 49 91 77 65 95 85 57 93 87 69 62 94 86 82 74 27 63 45 75 50 30 90 42 70 28 92 84 76 68 60 56 52 78 44 66 32 80 48 72
 97 [2691 : 2062]  97 49 91 77 65 95 85 57 93 87 69 62 94 86 82 74 27 63 45 75 50 30 90 42 70 28 92 84 76 68 60 56 52 78 44 66 32 80 48 72
 98 [2813 : 2038]  97 49 91 77 65 95 85 57 93 87 69 62 98 94 86 82 74 28 92 76 68 56 52 44 32 27 63 45 75 50 70 42 84 78 66 54 90 60 80 48 72
 99 [2830 : 2120]  97 49 91 77 65 95 85 57 93 87 69 62 98 94 86 82 74 28 92 76 68 56 52 44 32 27 99 66 78 63 54 45 75 50 90 70 40 60 84 48 72
 100 [2970 : 2080]  97 49 91 77 65 95 85 57 93 87 69 62 98 94 86 82 74 28 92 76 68 56 52 44 32 27 99 66 78 63 54 45 75 50 100 90 80 70 60 84 48 72

And one more thing...

A nearly optimal score of $3162$ for $n=100$ with this sequence:
97 49 91 65 95 85 57 87 93 62 94 86 82 74 69 77 98 81 63 42 99 54 66 45 75 50 70 90 100 60 84 56 64 96 72 80 88 52 78 68 76 92
OEIS A019312 lists the optimal score as $3164$

Answer 2

If I am not mistaken this is simply the game Taxman or Zahlenhai.

After $n = 847$ a general algorithm will solve this problem for every $n$.

• Repeat the same following step for $p = 5, 3, 2$.
• Consider all pairs $(x, px)$ with $px \leq N$ in descending order and pick every pair that does not share a value with already chosen pairs.
• At the end of this procedure, you will want to pick the higher value in every pair, with the noob always getting at least the lower number in the pair. These numbers can always be picked in some order without issue, by considering them by increasing number of prime factors (counted with multiplicity). Ties are resolved by picking the pair that won't interfere with the other picks with the same number of prime factors.

Showing that such a tie-resolving pick exists is much less obvious.

The details are in my paper "The difficulty of beating the Taxman", in which I show (among other things) that the game can be won for all n not equal to 1 or 3. There I also give a more complicated strategy that works for almost all n from 4 to 1000, and the winning moves for every exception.

Answer 3

PARTIAL ANSWER

Here is a winning strategy for $n=100$

Take $97,$ even numbers $100-68, 64, 60,56,52,99,93,87,81,75,69,63,95,85,91$. This gives a total of $2595$ coins, over half of the $5050$ in play. As Daniel Mathias says, you start with the largest prime, then take the even numbers down to $\frac {2n}3$ with half the number the witness that you can take it, then take multiples of $4$ from $\frac {2n}3$ to $\frac n2$. You skip the numbers equivalent to $2 \pmod 4$ in the bottom range because you want the number $\frac 32$ times as large in the next step. For example, we skip $62$ because it would use $31$ and we want $93$. We don't skip $60$ because $90=2 \cdot 45$ will still be available. We then take the available multiples of $3$ down to $63$, and finally $95,85,91$. I don't know if this approach will always win. There are more points available from small numbers before you do the series I listed. I don't know if they are ever necessary to win.