On the Existence of Optimal Strategies in a Combinatorial Game

2025

Read On the Existence of Optimal Strategies in a Combinatorial Game (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-2508-00246.txt.

Introduction

Tim Rammenstein settles who wins a number-removal game born in a German national mathematics competition. Two players take turns deleting numbers from a finite set of naturals, each aiming at a divisibility condition. Rammenstein generalizes the contest with two dials: the size of the starting set and a fixed divisor.

In his 2025 paper, broad families of the game are solved outright. With an even-sized starting set, the second player can always force a win, whatever the first does. Across many odd-sized cases, the first player holds the winning strategy instead. A web version of the game lets readers test the verdicts by hand. The paper turns a contest puzzle into a small, complete theory of optimal play.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-00246

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Existence of Optimal Strategies in a Combinatorial Game Abstract We study a combinatorial game derived from a problem in the German National Mathematics Competition. In this game, two players take turns removing numbers from a finite set of natural numbers, aiming to satisfy a certain divisibility condition. We introduce a generalized version of the original game, which depends on two parameters: the size of the initial number set and a fixed divisor. For both players, we identify a broad range of game variants in which they can force a win. In particular, we show that for even-sized sets, the second player to move can always win, while for many odd-sized cases, the first player to move has a winning strategy. A web implementation of the game demonstrates some of our results in practice. Tim Rammenstein Introduction In a problem from the 2017 Bundeswettbewerb Mathematik (German National Mathematics Competition) [ 1 ] , a game is described in which two players compete, and the task is to determine which player can force a win. During a project-based school week, the game was simplified so that it could be played quickly against others, while still allowing one player to have a guaranteed winning strategy. The game can be further generalized by treating its two key parameters as variables. In this paper, we analyze the generalized variants of the game and rigorously justify the optimal strategies found in the course of analyzing the game. In doing so, statements are established that guarantee the existence of an optimal strategy for a wide range of game variants. Complementing the theoretical work, a website was created where variants of the game – which I have named Zahlenschlacht (this roughly translates to “Number Battle“) – can be played. What makes the game Zahlenschlacht especially interesting are its simple gameplay and its short duration. Through finitary relations and number theory, particularly modular arithmetic, concepts of the game can be mathematically modeled and effectively studied. Foundations of the Game In this section, the game is introduced in its original form [ 1 ] as well as in a simplified variant. After briefly situating the game within the domain of game theory, a generalization of the game is presented. Subsequently, fundamental game concepts are formalized mathematically, which is essential for the strategies and proofs in Section 3 . Rules of the Game The game Zahlenschlacht is a two-player game. Players take turns crossing out numbers displayed on a surface, such as a blackboard (hereafter referred to as the board ). The act of crossing out a number is referred to as a ‘move‘. Original Game The numbers 1, 2, 3, …, 2017 are placed on the board. Player A and Player B take turns crossing out one number at a time until just two numbers remain. A begins. If the sum of the two remaining numbers is divisble by 8, A wins; otherwise, B wins. [ 1 ] As shown in [ 2 ] , A can force a win. For this, A needs to play in accordance with the following strategy: A crosses out, as the first move, a number that leaves a remainder of 1 when divided by 8, for example, the number 2017. Afterwards, for each number crossed out by B , A crosses out a number such that the sum of the two numbers is divisible by 8. Game Variant As part of a project-based school week, I searched for a simplified and easily playable variant of the original game in which one player can force a win. The following variant was developed in the process: The numbers 1, 2, 3, …, 15 are placed on the board. As in the original game, numbers are crossed out until just two remain. If the sum of the two remaining numbers is divisible by 7, A wins. Otherwise, B wins. Figure 1: Visual representation of the board consisting of 15 numbers Here too, A can force a win – using a strategy similar to that in the original game: A crosses out, as the first move, one of the numbers 1, 8 or 15. Then, after each move of B , A crosses out a number such that the sum of both chosen numbers is divisible by 7. That A can force a win using this strategy, is proven in Section 3 . Game-theoretic Classification In contrast to cooperative games, where players can form binding agreements to maximize a common benefit, players in non-cooperative games act independently and pursue their own interests. Zahlenschlacht belongs to the latter category. The game is played as follows: Two players transform an initial position into a final position through a finite number of alternating moves, at which point a unique winner is determined (a draw is excluded, as the sum of the last two remaining numbers is either divisible by a fixed number or not). Accordingly, Zahlenschlacht falls into the category of combinatorial games [ 3 ] – deterministic two-player games with alternating, well-defined moves and perfect information. Furthermore, it is an impartial game, as Player A and Player B can make the same moves from the same game position. Generalization of the Game The difference between the game variant in 2.1.2 and the original game in 2.1.1 lies only in the number of elements on the board and the number that decides the winner based on whether the sum of the last two numbers is divisible by it. Let n\in\mathbb{N} be the number of elements on the board. Clearly, it is reasonable to exclude n=1 , since in this case no two numbers could remain at the end. Likewise, n=3 is also not to be considered, as the game would consist of only a single move and thus would not qualify as a two-player game. In Section 3.2 , it is shown that for any even n , Player B can force a win. Since this result holds for every second natural number, the focus of this paper lies on the considerably more interesting variants with odd n . Let d\in\mathbb{N} be the number that decides the winner based on whether the sum of the last two numbers is divisible by it. We assume d\geq 2 , since for d=1 , Player A trivially wins. The parameters n and d define a generalization of the game from [ 1 ] , enabling the formulation of all meaningful variants. Definition 2.3.1 . Let n , d \in\mathbb{N} , with n\geq 4 and d\geq 2 , be fixed. We denote by \textit{Z}(n,d) the two-player game with the following rules. • The board consists of the first n natural numbers in ascending order, 1 , …, n . • Player A and Player B take turns crossing out numbers until only two numbers remain. Player A begins. • If the sum of the two remaining numbers is divisible by d , Player A wins. Otherwise, Player B wins. Unless stated otherwise, the numbers n and d are defined according to Definition 2.3.1 throughout the remainder of this paper. Example 2.3.2 . Section 2.1.1 discusses the game \textit{Z}(2017,8) , Section 2.1.2 discusses the game \textit{Z}(15,7) . In both games, A can force a

Read the complete text