2
$\begingroup$

The motivation for this question came from a game introduced in a math(s) class, and so I thought it would be interesting to see if one could develop a winning strategy.


Let $S$ be a multiset $[a_1,a_2,\dots,a_n]$, with $ a_i\in\mathbb{N}=\{0,1,2,3,\dots\}$. A game is played on $S$ where two players take turns to play single moves where a move consists of the following:

Replace an element $a\in S$ with $b,c\in\mathbb{N}$, such that $b+c<a$.

The last player to (be able to) make a (legal) move loses the game, i.e: s/he leaves each element of $S$ as zero.

This can be though of (and indeed was originally presented to me) as a misère Nim-like game where the elements of $S$ indicate the inital number of objects in $n$ heaps, and, where in normal Nim a move consists of removing some number of objects from the end of a heap, instead in this game you can remove a contiguous run of objects from anywhere in the heap, potentially separating the heap into two separate, non-empty heaps.


Given the simplicity, I imagine there exists a winning strategy, for the first or second player depending on the initial $S$. However, I have never studied games mathematically, and don't really how to go about development of a winning strategy - this is my first point of enquiry. The second (or maybe zeroth) being: is this equivalent to an existing (well-understood?) mathematical game?

After some intial analysis of my own, I determined $[1,1,1]$, $[2,2]$, and $[1,1,2,2]$ is won by the second player, and thus $[1,2,5]$ is won by the first player.

$\endgroup$
8
  • 1
    $\begingroup$ This would be the octal game $0.\dot7$. Surprisingly, a first glance through the literature doesn't reveal any information about it. I can't imagine why there wouldn't be, as it's simple enough that you would think it would be named after someone by now. $\endgroup$
    – user694818
    Dec 16 '19 at 11:58
  • 1
    $\begingroup$ $[2,2]$ (like any "symmetric" position) should be a win for the second player by simply stealing the first player's strategy. So $[1,2,X]$ is a win for the first player whenever $X>3$ by reducing the position to $[1,1,2,2]$. $\endgroup$
    – user694818
    Dec 16 '19 at 12:07
  • $\begingroup$ Yes - sorry I mis-interpreted my notes: let me correct $\endgroup$ Dec 16 '19 at 12:09
  • $\begingroup$ @MatthewDaly you expect a solution... though none has been found? $\endgroup$ Dec 16 '19 at 12:13
  • $\begingroup$ Some octal games have complete solutions and others with equally clear rules don't. I wouldn't venture a guess in this case. $\endgroup$
    – user694818
    Dec 16 '19 at 12:22
2
$\begingroup$

I think a player wins if they leave a position consisting of either an odd number of 1s or numbers, not all 1s, with zero nim sum.

Proof If left such a position with zero nim sum but not all 1s then your move will leave a position with not all 1s and non-zero nim sum.

If left a position with not all 1s and non-zero nim sum then make the nim sum zero unless the position consists of 1s apart from one number. In that case reduce the larger number to zero/one to make the nim sum non-zero.

$\endgroup$

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.