25
$\begingroup$

Edit (Nov 1, 2015): Bounty awarded, but the full question (i.e., what is the optimal strategy) remains open at the time of this update.


Consider the Factor Game played as follows:

Given a list of positive integers $1, \ldots, n$, two players (red and blue) alternate turns.

On each turn, the player picks and circles (in their color) any un-circled number $k$ that has at least one proper divisor yet to be circled; their opponent responds by circling (in their own color) all remaining proper divisors of $k$.

Then they switch (colors adjusted accordingly) and the game continues until there are no legal moves remaining.

At that point, each player adds up their circled numbers and the greater sum wins.

Question: What is the optimal strategy in the Factor Game?

My guess is that, for large enough $n$, picking the number that nets the most points on each individual turn is optimal. For example, if $n = 49$, then the first player would pick $47$ (to net $46$) and their opponent would respond with $49$ (to net $42$). But this strategy is admittedly short-sighted.

(Clearly the strategy fails for some small choices of $n$ (the example of $n = 4$ is provided in the comments; $n = 9$ is another failure) but I'm okay with assuming $n$ is sufficiently large.)

I am hoping for a description of an optimal strategy and a proof that it is optimal (for $n$ large enough), but would be interested in special cases, heuristic arguments for what would be an optimal strategy, and heuristic arguments for why this problem is difficult.


Motivation: This game is sometimes played in elementary schools (or, in my classes, with elementary school teachers) to explore concepts like prime, composite, divisor, proper divisor, etc. In such a case, the numbers are usually presented in an array - often a square array, and so my particular interest is when $n$ is a square.

You can play the Factor Game through the NCTM (National Council of Teachers of Mathematics) Illuminations site if you would like to experience it for yourself.

Here is a sample board when $n = 49$ (presented as a $7 \times 7$ array):

enter image description here

$\endgroup$
  • 4
    $\begingroup$ The fact that there's a grid doesn't matter, does it? The game plays out exactly the same on, say, a, 10-by-6 grid and a 15-by-4 grid, which both have 60 squares. $\endgroup$ – Michael Lugo Oct 23 '15 at 21:02
  • 2
    $\begingroup$ So then is there something special about the largest number being a square? Why even have the grid, why not just a list of the numbers $1\ldots n^{2}$? $\endgroup$ – Morgan Rodgers Oct 23 '15 at 21:44
  • 3
    $\begingroup$ I honestly believe that the fact that $n$ is assumed a square is purely practical for the recreational game and is of no interest in the actual problem. $\endgroup$ – Patrick Da Silva Oct 24 '15 at 1:32
  • 3
    $\begingroup$ The "pick the number netting the most points" strategy is not optimal for the $2\times 2$ game. Using this strategy, red picks $3$, blue gets $1$, blue picks $4$, red gets $2$, tie game. Red can win by picking $2$ or $4$ to start. $\endgroup$ – Julian Rosen Oct 24 '15 at 1:59
  • 2
    $\begingroup$ By "optimal strategy" do you mean a strategy that produces the largest possible margin of victory, or are you satisfied with (possibly simpler) strategies that only guarantee a win (or, to be precise, a non-loss, since ties appear to be possible)? $\endgroup$ – Barry Cipra Oct 28 '15 at 14:47
10
+50
$\begingroup$

Clean-up on previous edits

The greedy strategy may be described, as stated in the OP, for large enough $n$, as locally optimal number-picking so as to net the most points on each individual turn.

This fails for $1\leq n\leq 500$ for the following $n:$

$$4, 9, 25, 28, 29, 42, 52, 53, 54, 58, 59, 60, 61, 66, 77, 86, 102, \ 103, 104, 108, 109, 114, 115, 117, 122, 123, 161, 162, 176, 177, 182, \ 183, 184, 185, 187, 189, 194, 195, 210, 211, 216, 217, 221, 228, 229, \ 238, 239, 243, 245, 247, 248, 249, 273, 282, 283, 286, 287, 288, 289, \ 292, 293, 298, 310, 311, 312, 313, 324, 325, 330, 331, 333, 338, 339, \ 343, 344, 345, 350, 351, 354, 355, 363, 364, 365, 369, 374, 375, 376, \ 382, 383, 384, 385, 387, 391, 392, 395, 396, 397, 405, 407, 408, 409, \ 412, 413, 414, 415, 420, 421, 429, 432, 433, 436, 437, 442, 443, 444, \ 445, 452, 453, 458, 466, 467, 477, 482, 487, 488$$

In these cases (where for the original "greedy strategy", one would pick the highest prime in the range to open the game), pick the highest odd semiprime in the range. From the opening choice onward, play the greedy strategy. This strategy results in a win for player $1$ for all $n\leq 500.$

With this approach, it is possible to avoid the "play low" game as described below, along with its obvious pitfalls.

Using the MMA code in the link below, one can find all opening numbers that give a win for player one (and thereafter playing as per local optimal strategy). Taking $n=25$, for example, which fails to give a win using the local optimal strategy,

With[{nn = 25}, 
Select[Transpose@{Range[2,nn],c4R[s1,nn,#] &/@ Range[2, nn]}, #[[2]] > 0&]]

%[[All, 1]]

gives $5, 7, 11, 25$ (hence, choose $25$ as the opening play since it is the largest odd semiprime in the given range) as the winning opening numbers for player $1$.

Likewise, testing the numbers that fail on the prime openings:

With[{nn = #}, c4R[s1, nn, Max@Select[Range@nn, OddQ@# == True && 
PrimeOmega@# == 2 &]]] & /@ {9, 25, 28, 29, 42, 52, 53, 54, 58, 59, 60, 61, 
66, 77, 86, 102, 103, 104, 108, 109, 114, 115, 117, 122, 123, 161, 162, 176, 
177, 182, 183, 184, 185, 187, 189, 194, 195, 210, 211, 216, 217, 221, 228, 
229, 238, 239, 243, 245, 247, 248, 249, 273, 282, 283, 286, 287, 288, 289, 
292, 293, 298, 310, 311, 312, 313, 324, 325, 330, 331, 333, 338, 339, 
343, 344, 345, 350, 351, 354, 355, 363, 364, 365, 369, 374, 375, 376, 
382, 383, 384, 385, 387, 391, 392, 395, 396, 397, 405, 407, 408, 409, 
412, 413, 414, 415, 420, 421, 429, 432, 433, 436, 437, 442, 443, 444, 
445, 452, 453, 458, 466, 467, 477, 482, 487, 488}

results in all positive values.

Original answer

Modifying the first choice to $2$ (as opposed to the largest prime in the range) where the "short-sighted" solution fails appears to be the winning strategy.

However, this does not hold for $n=77$:

Select[With[{aa = Select[Transpose@{Range@200, aa}, #[[2]] < 0 &]
[[All, 1]]}, Transpose@{aa, (Sign@bb)[[#]] & /@ aa}], #[[2]] < 0 &][[All, 1]]

strat[n] for any $n\geq30$ should then force a win for player $1$ for most $n$. Note that player $2$ plays the local optimal strategy, but, though I would be surprised if an alternative strategy could force a win for player $2$, this possibility is yet to be explored.

Note

Of course, since the game will be reversed if player $1$ chooses $1$ to start, and in so doing, allows player $2$ to go first, if player $2$ plays by the same strategy, he will choose $2$, etc., making the game rather absurd. A rule that either player may not forfeit a turn should then be adhered to, if a sensible solution is to be arrived at.

Added

I believe that the local strategy results in the longest game for large enough $n$. Interestingly, the length of the game for the local strategy for each $n\sim n/e:$

enter image description here

dd = {0, 0, 0, 0}~Join~(Length@s4[s1, #, Max@Select[Range@#, PrimeQ]] & /@ 
Range[5, 200]); ListLinePlot[{dd, Range@200/E}]

Mathematica code available here.

$\endgroup$
  • 2
    $\begingroup$ @BenjaminDickman sure - will add in a bit :) $\endgroup$ – martin Oct 27 '15 at 23:39
  • $\begingroup$ @BenjaminDickman ran a test on opening with $1$ as opposed to $2,$ and shows complete symmetry as expected. Do you still want me to update with previous methods for $n<30?$ $\endgroup$ – martin Oct 28 '15 at 0:15
  • 2
    $\begingroup$ No, I'll just go through the edited versions if I need it. The direction the problem has gone is somewhat surprising... I think a proof of the symmetry with $1$ permissible is not too tough to sketch out [possibly just a sentence or two]. I'll give it some thought at another moment [unless someone else does, first]... $\endgroup$ – Benjamin Dickman Oct 28 '15 at 0:19
  • 2
    $\begingroup$ @BenjaminDickman there was an error with allowing $1$ to be selected, in that the code allowed $1$ to be selected twice. I hve ammended the answer accordingly, but of course, if this was the case, choosing $1$ first simply reverses who goes first! $\endgroup$ – martin Oct 28 '15 at 9:35
  • 1
    $\begingroup$ @BenjaminDickman I thought the odd semiprime strategy was an improvement on the play low one, since the play low one could well have become far more complicated tactically. I can't see any way this technique can be beaten (unless of course it fails for larger $ n, $ which I supect it might). The immediate downvote that came following that update left me thinking that I must have missed something, but perhaps you are right - not all downvotes are entirely explicable! Of course it is sensible to leave the question visable on the bounty list in case you get a better answer in the meantime :) $\endgroup$ – martin Oct 30 '15 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.