# 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
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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) ...
0answers
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 ...
0answers
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 ...
0answers
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. ...
0answers
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 ...
0answers
95 views

0answers
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, ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
71 views

0answers
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 ...
0answers
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 ...
0answers
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}$...
0answers
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 ...
0answers
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'...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
96 views

### Finding a Mathematical definition of a Discrete Time Game

Preface: Suppose we have a game world as depicted in the following figure: Where each of the white blocks is passable, And each of the black blocks is a wall and so impassable. Each of the Green ...
0answers
256 views

### The hardest game of mahjongg

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 ...