# Questions tagged [combinatorial-game-theory]

Combinatorial game theory (abbreviated CGT) is the subfield of combinatorics (not traditional game theory) which deals with games of perfect information such as Nim and Go. It includes topics such as the Sprague-Grundy theorem and is tangentially related to the Surreal Numbers.

170 questions
13k views

### The Ring Game on $K[x,y,z]$

I recently read about the Ring Game on MathOverflow, and have been trying to determine winning strategies for each player on various rings. The game has two players and begins with a commutative ...
667 views

### Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple. Disconnect. Players alternately remove vertices from a ...
677 views

### “Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
361 views

### Strategy for board game 2

In this question the following was asked: Alice and Bob are playing the following game: They have a $4 \times 4$ empty grid and take turns coloring one square each, starting with Alice, both using ...
346 views

### NIM with multiple winning final positions

I've been looking at a variant of NIM. You can skip this bit where I'll describe NIM as usually described: There's a starting position with some number of piles of counters and two players ...
141 views

### Broken stick game

Two players Alice and Bob play the following game consisting of $n-1$ turns. Initially the segment $[0,1]$ is given. Alice and Bob then alternate breaking one segment into two pieces. After all turns ...
155 views

### Has this subset-sum game been studied?

Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their ...
282 views

### Prime number building game

Players $A$ and $B$ choose digits $(0, \dots , 9)$ turn by turn and build number by concatenating the digit they chose to the end of the number. Player $A$ starts by picking the first (one-digit) ...
867 views

### Chat Noir solvable?

There is a relatively simple flash game that I enjoy playing -- http://www.gamedesign.jp/flash/chatnoir/chatnoir.html is one version of it, though I've found many -- and it centers around trying to ...
231 views

### British Maths Olympiad (BMO) 2004 Round 1 Question 4 alternative solutions?

The question states: Alice and Barbara play a game with a pack of $2n$ cards. On each of which is written a positive integer. The pack is laid out in a row, with the numbers facing upwards. Alice ...
61 views

### Question about proportion of Nim positions

Let a Nim game be represented by a sequence of positive integers. We call a Nim of size $n$ when the sum of its elements is $n$. Let $a(n)$ be the number of Nim games of size $2n$ with Nim sum 0. ...
106 views

### Improper integrals over the reals and surreal numbers

Is it possible to assign improper integrals over the reals a surreal value in a consistent way? Are there any papers available on this? Note that I am not inquiring about formalizing integration over ...
95 views

275 views

### Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
172 views

### Number Theoretic Game

2 players A and B play a game. At the start of the game, $n$ positive integers (not necessarily distinct) are written on a notebook. First, player A chooses a number from the notebook and declares it ...
57 views

### Solving the Matrix Game

Let $\{v_j\}_j$ be a collection of $n$ column vectors $v_j \in \mathbb{F}_2^{r}$ s.t. the matrix built from those has no zero rows. Now we play a game: You have 3 options: You may drop any column ...
142 views

### Andrew and Ben play on graph

Given complete graph with $n$ vertices. Andrew in his turn removes exactly one edge and Ben in his turn removes two or three edges. They take turns one after another and Andrew begins. The player ...
71 views

32 views

### The smallest-sum game

The game is a function of an integer $n\geq 1$ and a number $t\in(0,n)$. An adversary picks $n$ numbers in $[0,1]$ whose total sum is $t$. You divide the numbers into two subsets and the adversary ...
20 views

### A simple game with $n$ points in 3D space - red triangle wins

(Once again a son is torturing his father...) Alice and Bob play a fairly simple game with $n$ predefined points in 3D space. No four points are complanar (which also implies that no three points are ...
80 views

### King of the Centre - Is this an existing game?

Consider an $n$-player infinitely repeated game. First stage nature chooses for each player, $i$, a radius $r_{i}$. For each later stage $t$ each player $i$: The payer chooses a "target" $p_{i, t}$...
68 views

### Queens on a torus chessboard.

Consider a Torus chessboard $\mathbb T$ of dimension $8\times8$. How much queens it is possible to put on in such a way that no one attacks another? (I assume we use the same rules of standard ...
91 views

### Math problem from logical game

We have a set of arrows and can start from any point. Every next point must be chosen in direction of previous and can be used only one time. We need to visit all points. Direction of last point doesn'...
52 views

### Given a linear path with $n$ dots connected by $n-1$ lines, find the minimum number of coins required to win the game

Given a linear path with $n$ dots connected by $n-1$ lines, find the minimum number of coins required to win the game provided the game features are as follows: In the following game, you're given a ...
224 views

### Game on triples of integers modulo 3n

Consider the following game played on triples of integers modulo $3n$. Player $B$ writes down the triple $(a,a+n,a+2n)$. Starting with player $A$, they then take it in turns to add $1$ to one of the ...
244 views

### Distributed Assignment Problem for resource allocation

I am working on a resource allocation problem, which is formulated as an 'assignment problem'. It is solved using Hungarian Method. Let's assume that below is my assignment problem, where each ...
124 views

### Universal algorithm to win a turn-based math game

One of my friends suggested me to play a game. It is a turn-based math game that requires 2 players. Here are the rules: Both players propose a 4-digits number. Then, using a coin, they decide who ...
454 views

### A variation of Nim game

There are two players $X$ and $Y$. They write $N$ integers on paper $( A_1 , A_2 , A_3 , .... A_N )$. They have also $M$ integers $(B_1 , B_2 , B_3 , .... B_M )$ . Now, Player $X$ always takes ...
I was playing Mahjongg solitaire the other day. It got me thinking... The board has $2n$ pieces at the beginning and assuming that the game is winnable. The game would be trivial if there would be ...