Intereting Posts

From constrained to unconstrained maximization problem
Closed form for $\sum\limits_{k=1}^{\infty}\zeta(4k-2)-\zeta(4k)$
Can someone explain Cayley's Theorem step by step?
Sequence converges iff $\limsup = \liminf$
Show that $m+3$ and $m^2 + 3m +3$ cannot both be perfect cubes.
If $|A|=30$ and $|B|=20$, find the number of surjective functions $f:A \to B$.
Puzzled by $\displaystyle \lim_{x \to – \infty} \sqrt{x^2+x}-x$
Visualization of Singular Value decomposition of a Symmetric Matrix
How to prove the optimal Towers of Hanoi strategy?
$\aleph_1 = 2^{\aleph_0}$
$F:G\to B$ is an isomorphism between groups implies $F^{-1}$ is an isomorphism
Is $G/pG$ is a $p$-group?
Proof Check: Number of elements of $\mathbb{F}_{p^{n}}$ of the form $a^{p}-a$ for some $a \in \mathbb{F}_{p^{n}}$.
Finding the convergence interval of $\sum\limits_{n=0}^{\infty} \frac{n!x^n}{n^n}$.
How do I solve this improper integral: $\int_{-\infty}^\infty e^{-x^2-x}dx$?

We have an $n$-gon with $n\geq 3$. Players $A$ and $B$ place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has a winning strategy?

If $n$ is even, $B$ can win by placing a stone at a vertex diametrically opposite the vertex that $A$ just placed a stone on. For $n=3,7$, $A$ wins, but for $n=5$, $B$ wins.

- Name for a certain “product game”
- Extending Conway Games to $n$ players
- Trying to find the name of this Nim variant
- board game: 10 by 10 light bulbs, minimum switches to get all off?
- Exceptional values in a combinatorial game
- It seems like a nim variant

- Show that $C(n,k) = C(n-1,k) + C(n-1,k-1)$
- sum of all the numbers that can be formed using the digits 2,3,3,4,4,4..
- The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by
- How many 90 ball bingo cards are there?
- Proving formula for sum of squares with binomial coefficient
- Number of invertible 0-1 matrices
- Help me solve a combinatorial problem
- Maximum integer not in $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$
- Probability of a substring occurring in a string
- A simple permutation question - discrete math

It turns out that this game is very closely related to a well-known game known as Dawson’s Chess, which is equivalent to the Octal Game with code “0.137”. Using the Sprague-Grundy Theorem combined with a winning strategy for Nim, it is relatively straightforward to analyze small games like this (e.g. your game for small $n$), and with a tool known as the “(Guy-Smith) Octal Periodicity Theorem”, some Octal games, including this one, become easy to give a relatively efficient computer strategy for *all* $n$. It turns out that $A$ has a winning strategy for $n\equiv7,11,23,27,31\text{ mod }34$ and in the three exceptional cases $n=3$, $n=17$, and $n=37$. In all other cases, $B$ has a winning strategy.

Note that the first move always removes three vertices from consideration, and leaves a consecutive run of $n-3$ available vertices. After that, we don’t have to worry about polygons/circles anymore, as all of the following game states will just involve zero or more consecutive runs. You can play this game on some small runs at Tom Ferguson’s “Dawson’s Chess” page. Note that $A$ has a winning strategy on an $n$-gon precisely if the next player to move on a run of $n-3$ vertices does *not* have a winning strategy.

To connect this game to existing general theory, we can reconceptualize it: instead of placing stones on runs which often eliminate possibilities of placing stones in the adjacent spots, imagine there are stones already there and when you pick a stone to remove, you remove any adjacent stone(s) as well (as if the Xs and Os on Tom’s Dawson’s Chess page all represent removed stones).

You can remove one stone from a run precisely if the run was only one stone long, so that you leave **zero runs** behind. You can remove two stones from a run if it’s at the end of the run, so you that you leave **zero or one** runs behind. You can remove three stones from a run anywhere, so you can leave **zero or one or two** runs behind (and those two runs can have any lengths that add up to the right total). You can never remove more than three stones from a run. Games with rules like these are traditionally encoded in a “number” with Octal digits. In this case, the code is $0.(2^0)(2^0+2^1)(2^0+2^1+2^2)=0.137$.

Since the original question was “who has a winning strategy?”, rather than “what is the winning strategy, I won’t re-present an introduction to the relevant theorems in detail.

If you don’t already know about the strategy for Nim or the Sprague-Grundy Theorem and how they can be applied to similar games, you can read one or more of the following:

- Tom Ferguson’s class notes on the subject
- MJD’s notes in their tidy blog post about using this theory to solve the game in the question for $n$ up through $23$.
- Lim Chu Wee’s series of blog posts which are also class notes building up the relevant theory (posts I through V)
- The lecture notes Misère Games and Misère Quotients by Aaron N. Siegel through page 10.
- My own long-winded series of blog posts building up the relevant theory (posts I.1 through I.6).
- Chapter 7 of the undergraduate textbook “Lessons in Play: An Introduction to Combinatorial Game Theory” by Albert, Nowakowski, and Wolfe (although a bit of reading of other chapters may be needed first).

Because of the strategy for Nim (how Grundy values combine), it suffices to know the Grundy/Nim values for a single “heap” (in our context, a run of stones). If you calculate enough of these, you will see a pattern. The sequence appears to be eventually periodic. For Octal games, there is a theorem attributed to Guy and Smith that says an apparent periodicity that goes on for long enough is guaranteed to continue forever. You can read about it on page 11 of Misère Games and Misère Quotients by Aaron N. Siegel, in this blog post of mine or as Theorem IV.2.7 in the graduate textbook “Combinatorial Game Theory” by Aaron N. Siegel.

In the case of the game 0.137, checking the values for runs/heaps of length up to 180 is enough to confirm that the pattern continues forever. The following is a table of the values for a run of length $m$ for $0\le m\le135$ (read top to bottom, left to right) with exceptional values undelined:

\begin{array}{r|cccc}

m & \text{0+} & \text{34+} & \text{68+} & \text{102+} \\

\hline

0 & \underline{0} & \underline{0} & 8 & 8 \\

1 & 1 & 1 & 1 & 1 \\

2 & 1 & 1 & 1 & 1 \\

3 & 2 & 2 & 2 & 2 \\

4 & 0 & 0 & 0 & 0 \\

5 & 3 & 3 & 3 & 3 \\

6 & 1 & 1 & 1 & 1 \\

7 & 1 & 1 & 1 & 1 \\

8 & 0 & 0 & 0 & 0 \\

9 & 3 & 3 & 3 & 3 \\

10 & 3 & 3 & 3 & 3 \\

11 & 2 & 2 & 2 & 2 \\

12 & 2 & 2 & 2 & 2 \\

13 & 4 & 4 & 4 & 4 \\

14 & \underline{0} & 4 & 4 & 4 \\

15 & 5 & 5 & 5 & 5 \\

16 & \underline{2} & 5 & 5 & 5 \\

17 & \underline{2} & \underline{2} & 9 & 9 \\

18 & 3 & 3 & 3 & 3 \\

19 & 3 & 3 & 3 & 3 \\

20 & 0 & 0 & 0 & 0 \\

21 & 1 & 1 & 1 & 1 \\

22 & 1 & 1 & 1 & 1 \\

23 & 3 & 3 & 3 & 3 \\

24 & 0 & 0 & 0 & 0 \\

25 & 2 & 2 & 2 & 2 \\

26 & 1 & 1 & 1 & 1 \\

27 & 1 & 1 & 1 & 1 \\

28 & 0 & 0 & 0 & 0 \\

29 & 4 & 4 & 4 & 4 \\

30 & 5 & 5 & 5 & 5 \\

31 & \underline{2} & 3 & 3 & 3 \\

32 & 7 & 7 & 7 & 7 \\

33 & 4 & 4 & 4 & 4 \end{array}

Since Dawson’s Chess is so well known, this sequence is A002187 at the On-line Encyclopedia of Integer Sequences. Since $0$ is the only Grundy value corresponding to a second-player win in Dawson’s Chess, they represent values $m$ for which $A$ wins the polygon game on an $m+3$-gon. Since the pattern repeats forever, the win/loss result is as stated in the beginning:

$A$ has a winning strategy for $n\equiv7,11,23,27,31\text{ mod }34$ and in the three exceptional cases $n=3$, $n=17$, and $n=37$. In all other cases, $B$ has a winning strategy.

- Is there a shape with infinite area but finite perimeter?
- Show that $ \mathbb{E} < \infty \Longleftrightarrow \sum_{n=1}^\infty \mathbb{P} < \infty $ for random variable $X$
- Cokernel of a Composition.
- Homology of connected sum of real projective spaces
- Prove that $ \left(1+\frac a b \right) \left(1+\frac b c \right)\left(1+\frac c a \right) \geq 2\left(1+ \frac{a+b+c}{\sqrt{abc}}\right)$.
- Odd binomial sum equality has only trivial solution?
- Problem with $Pullback$ Calculation
- Book on the Rigorous Foundations of Mathematics- Logic and Set Theory
- How to show $\ell^2_p$ not isometric to $\ell^2_{p'}$ unless $p\in\{1,2,\infty\}$?
- Number of cyclic paths in a rectangular grid?
- Understanding the Gram-Schmidt process
- Does $M_n^{-1}$ converge for a series of growing matrices $M_n$?
- Intuitive explanation with rigorous details why zeta has infinitely many zeros?
- Square of a second derivative is the fourth derivative
- When is $(a+b)^n \equiv a^n+b^n$?