A VARIANT OF GAME OF SLIDING COINS
Ryohei Miyadera · 2025
Read A VARIANT OF GAME OF SLIDING COINS by Ryohei Miyadera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18606.txt.
Introduction
Ryohei Miyadera and co-authors study a new twist on a coin-sliding game, in a 2025 paper. Two coins sit on a long strip of numbered squares, and players take turns sliding a coin to a lower free square. A coin pushed off the strip is lost from play. The twist adds a push move: the right coin can shove the left one as it moves.
That push makes the game hard to read, yet the team worked out formulas for its Grundy numbers, the scores that reveal who wins. With two coins alone, the first player always wins, so the game looks trivial. Joining two boards into one game restores real contest, and the formulas hand the winner a clear plan. The work adds a fresh case to the theory of impartial games.
Catalog record
| CREATOR | Ryohei Miyadera |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18606
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A VARIANT OF GAME OF SLIDING COINS Ryohei Miyadera Abstract Received: , Revised: , Accepted: , Published: Abstract Here, we present a variant of the sliding coins game. Two coins are placed on distinct squares of a semi-infinite linear board with squares numbered 0,1,2,dots, . Two players take turns and move a coin to a lower unoccupied square. When a coin is pushed to the outside of the linear board, the players cannot use this coin anymore. In this game, we have another operation of moving coins: moving the coin on the right leftward and pushing the coin on the left. This last operation complicates this game’s mathematical structure, but we have managed to make formulas for Grundy numbers. Since all the positions of this game of two coins are the next player’s winning position, this game of two coins is trivial as a game. However, by making the sum of two games, we get a meaningful game in which the player who plays for the last time is the winner. With these Grundy numbers formulae, we get the winning strategy. 1 A game of sliding coins Let \mathbb{Z}_{\geq 0} and \mathbb{N} be the sets of nonnegative and natural numbers, respectively. Definition 1.1 . There are two coins, and two players take turns and move one of the coins to leftward as in Figures 2 and 2 , or move the coin on the right to leftward and push also the coin on the left leftward as in Figure 4 . Players can also push one of the coins or both coins over the edge as in Figures 4 and 6 . Players cannot move the coin on the right over the coin on the left. See Figure 6 Definition 1.2 . We use two of the game in Definition 1.1 to make the game of four coins in Figure 7 . Players take turns and move coins on the left strap leftward, and coins on the right strap rightward. The player who plays for the last time is the winner. Figure 1: Figure 2: Figure 3: Figure 4: Figure 5: Figure 6: Figure 7: A game with two directions 2 Combinatorial Game Theory Definitions and Theorems For completeness, we briefly review some of the necessary concepts of combinatorial game theory by referring to [ 1 ] and [ 2 ] . Definition 2.1 . Let x and y be nonnegative integers. Expressing them in base 2, x=\sum_{i=0}^{n}x_{i}2^{i} and y=\sum_{i=0}^{n}y_{i}2^{i} with x_{i},y_{i}\in\{0,1\} . We define Nim-sum , x\oplus y , as follows: x\oplus y=\sum\limits_{i=0}^{n}{{w_{i}}}{2^{i}}, where w_{i}=x_{i}+y_{i}\ (\bmod\ 2) . As chocolate bar games are impartial games without drawings, only two outcome classes are possible. Definition 2.2 . (a) A position is referred to as a \mathcal{P} - position if it is a winning position for the previous player (the player who has just moved), as long as they play correctly at each stage. (b) A position is referred to as an \mathcal{N} - position if it is the winning position for the next player, as long as they play correctly at each stage. Definition 2.3 . The disjunctive sum of the two games, denoted by \mathbf{G}+\mathbf{H} , is a super game in which a player may move either in \mathbf{G} or \mathbf{H} but not in both. Definition 2.4 . For any position \mathbf{p} in game \mathbf{G} , a set of positions can be reached by one move in \mathbf{G} , which we denote as move (\mathbf{p}) . Definition 2.5 . (i) The minimum excluded value ( mex ) of a set S of nonnegative integers is the least nonnegative integer that is not in S. (ii) Let \mathbf{p} be the position in the impartial game. The associated Grundy number is denoted by G(\mathbf{p}) and is recursively defined by G(\mathbf{p})=\textit{mex}\{G(\mathbf{h}):\mathbf{h}\in move(\mathbf{p})\}. The next result demonstrates the usefulness of the Sprague-Brundy theory in impartial games. Theorem 1 . Let \mathbf{G} and \mathbf{H} be impartial rulesets, and G_{\mathbf{G}} and G_{\mathbf{H}} be the Grundy numbers of game \mathbf{g} played under the rules of \mathbf{G} and game \mathbf{h} played under those of \mathbf{H} . Thus, we obtain the following: (i) For any position \mathbf{g} in \mathbf{G} , G_{\mathbf{G}}(\mathbf{g})=0 if and only if \mathbf{g} is the \mathcal{P} -position. (ii) The Grundy number of positions \{\mathbf{g},\mathbf{h}\} in game \mathbf{G}+\mathbf{H} is G_{\mathbf{G}}(\mathbf{g})\oplus G_{\mathbf{H}}(\mathbf{h}) . See [ 1 ] or [ 2 ] for the proof of this theorem. 3 Sliding coins games First, we study Grundy numbers of the game of Definition 1.1 , and after that we study the game of Definition 1.2 . Definition 3.1 . (i) For n\in\mathbb{N} , let G_{n,1}=\{(a+\frac{2(n-2)}{3},a+\frac{4(n-2)}{3}+2):a\in\mathbb{Z}_{\geq 0}\}\text{ when }n=2\pmod{3} (1) and G_{n,1}=\emptyset\text{ when }n\neq 2\pmod{3}. (2) (ii) For n\in\mathbb{N} , let G_{n,2}=\{(a,n+\lfloor\frac{a+1}{2}\rfloor):a\in\mathbb{Z}_{\geq 0},a+\lfloor\frac{a+1}{2}\rfloor+1\leq n\text{ and }\lfloor\frac{a}{2}\rfloor=n\ (\bmod\ 2)\}. (3) (iii) For n\in\mathbb{N} , let G_{n,3}=\{(a,n-\lfloor\frac{a+1}{2}\rfloor):a\in\mathbb{Z}_{\geq 0},a+\lfloor\frac{a+1}{2}\rfloor+1\leq n\text{ and }\lfloor\frac{a}{2}\rfloor=n+1\ (\bmod\ 2)\}. (4) Lemma 1 . (i) Suppose that n=6m+2 for m\in\mathbb{Z}_{\geq 0} . Then, we have the following. G_{n,1}=\{(a+4m,a+8m+2):a\in\mathbb{Z}_{\geq 0}\}. (5) \displaystyle G_{n,2}= \displaystyle\{(4t,6m+2t+2):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+4\} \displaystyle\cup\{(4t+1,6m+2t+3):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+2\}. (6) \displaystyle G_{n,3}= \displaystyle\{(4t+2,6m-2t+1):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-1\} \displaystyle\cup\{(4t+3,6m-2t):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-3\}. (7) (ii) Suppose that n=6m+5 for m\in\mathbb{Z}_{\geq 0} . Then, we have the following. G_{n,1}=\{(a+4m+2,a+8m+6):a\in\mathbb{Z}_{\geq 0}\}. (8) \displaystyle G_{n,2}= \displaystyle\{(4t+2,6m+2t+6):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+1\} \displaystyle\cup\{(4t+3,6m+2t+7):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-1\}. (9) \displaystyle G_{n,3}= \displaystyle\{(4t,6m-2t+5):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+4\} \displaystyle\cup\{(4t+1,6m-2t+4):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+2\}. (10) (iii) Suppose that n=6m for m\in\mathbb{Z}_{\geq 0} . G_{n,1}=\emptyset. (11) \displaystyle G_{n,2}= \displaystyle\{(4t,6m+2t):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-1\} \displaystyle\cup\{(4t+1,6m+2t+1):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-3\}. (12) \displaystyle G_{n,3}= \displaystyle\{(4t+2,6m-2t-1):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-4\} \displaystyle\cup\{(4t+3,6m-2t-2):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-6\}. (13) (iv) Suppose that n=6m+1 for m\in\mathbb{Z}_{\geq 0} . G_{n,1}=\emptyset. (14) \displaystyle G_{n,2}= \displaystyle\{(4t+2,6m+2t+2):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-3\} \displaystyle\cup\{(4t+3,6m+2t+3):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-5\}. (15) \displaystyle G_{n,3}= \displaystyle\{(4t,6m-2t+1):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m\} \displaystyle\cup\{(4t+1,6m-2t):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-2\}. (16) (v) Suppose that n=6m+3 for m\in\mathbb{Z}_{\geq 0} . G_{n,1}=\emptyset. (17) \displaystyle G_{n,2}= \displaystyle\{(4t+2,6m+2t+4):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-1\} \displaystyle\cup\{(4t+3,6m+2t+5):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-3\}. (18) \displaystyle G_{n,3}= \displaystyle\{(4t,6m-2t+3):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+2\} \displaystyle\cup\{(4t+1,6m-2t+2):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m\}. (19) (vi) Suppose that n=6m+4 for m\in\mathbb{Z}_{\geq 0} . G_{n,1}=\emptyset. (20) \displaystyle G_{n,2}= \displaystyle\{(4t,6m+2t+4):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+3\} \displaystyle\cup\{(4t+1,6m+2t+5):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m+1\}. (21) \displaystyle G_{n,3}= \displaystyle\{(4t+2,6m-2t+3):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m\} \displaystyle\cup\{(4t+3,6m-2t+2):t\in\mathbb{Z}_{\geq 0}\text{ and }6t\leq 6m-2\}. (22) Lemma 2 . (i) If n=6m , then (4m-1,4m)\in G_{n,3} . (ii) If n=6m+1 , then (4m,4m+1)\in G_{n,3} . (iii) If n=6m+3 , then (4m+1,4m+2)\in G_{n,3} . (iv) If n=6m+4 , then (4m+2,4m+3)\in G_{n,3} . Proof. (i) Let a=4m-1 . Then a+\lfloor\frac{a+1}{2}\rfloor+1=4m-1+2m+1=6m\leq n , \lfloor\frac{a}{2}\rfloor=\lfloor\frac{4m-1}{2}\rfloor=2m-1 and n is odd. Hence, \lfloor\frac{a}{2}\rfloor=n+1\ (\bmod\ 2) . (a,n-\lfloor\frac{a+1}{2}\rfloor)=(a,6m-2m)=(4m-1,4m)\in G_{n,3}. (23) (ii) Let a=4m . Then a+\lfloor\frac{a+1}{2}\rfloor+1=4m+2m+1=6m+1\leq n , and (a,n-\lfloor\frac{a+1}{2}\rfloor)=(4m,6m-2m)=(4m,4m+1)\in G_{n,3}. (24) (iii) Let a=4m+1 . Then a+\lfloor\frac{a+1}{2}\rfloor+1=4m+1+2m+1+1=6m+3\leq n , and (a,n-\lfloor\frac{a+1}{2}\rfloor)=(a,6m+3-(2m+1))=(4m+1,4m+2)\in G_{n,3}. (25) (iv) Let a=4m+2 . Then a+\lfloor\frac{a+1}{2}\rfloor+1=4m+2+2m+1+1=6m+4\leq n , and (a,n-\lfloor\frac{a+1}{2}\rfloor)=(4m+2,6m+4-2m-1)=(4m+2,4m+3)\in G_{n,3}. (26) ∎ Lemma 3 . Suppose that you start with a position in G_{n,1} with n=2\pmod{3} . (i) You can move to a position in G_{n^{\prime},3} with n^{\prime}<n and n^{\prime}\neq 2\pmod{3} . (ii) You can move to a position in G_{n^{\prime},1} with n^{\prime}<n and n^{\prime}=2\pmod{3} . Proof. Suppose that we start with (x,y)\in G_{n,1} with n=2\pmod{3} . (i.1) If n=6m+2 , by ( 5 ) of Lemma 1 (x,y)=(a+4m,a+8m+2) . For n^{\prime}=6m^{\prime} , n^{\prime}=6m^{\prime}+1 with