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

666 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 ...
3answers
3k views

### Alice and Bob play the determinant game

Alice and Bob play the following game with an $n \times n$ matrix, where $n$ is odd. Alice fills in one of the entries of the matrix with a real number, then Bob, then Alice and so forth until the ...
3answers
6k views

### Sharing a pepperoni pizza with your worst enemy

You are about to eat a pepperoni pizza, which is sliced into eight pieces. Each pepperoni will unambiguously belong to some slice (no pepperoni is "between" slices). The caveat is that you have to ...
3answers
3k views

### Prime number construction game

This is a variant of Prime number building game. Player $A$ begins by choosing a single-digit prime number. Player $B$ then appends any digit to that number such that the result is still prime, and ...
4answers
4k views

### The expected outcome of a random game of chess?

Imagine a game of chess where both players generate a list of legal moves and pick one uniformly at random. Q: What is the expected outcome for white? 1 point for black checkmated, 0.5 for a draw, ...
9answers
76k views

### Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
3answers
1k views

### Three against the devil: a combinatorial game

A team of three sinners plays a game against the devil. They confer on strategy beforehand; then they go into three separate rooms, and there is no more communication between them. The play in each ...
3answers
2k views

### Guaranteed Checkmate with Rooks in High-Dimensional Chess

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb Z^n$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
1answer
792 views

### A 20+ year old combinatorial problem - the cookie game

Learned about this not too long after the time of the original problem publication through a classmate who visited MIT one summer. http://faculty.uml.edu/jpropp/cookie2.pdf The problem goes as ...
1answer
630 views

### Analysis of a combinatorial game with prime numbers

Many years ago, a coworker showed me a programming problem involving a combinatorial game with prime numbers that he had gotten somewhere or other. (For some reason, he refused to tell me the source.)...
1answer
2k views

### What is the optimal strategy in the “Factor Game”?

Edit (Nov 1, 2015): Bounty awarded, but the full question (i.e., what is the optimal strategy) remains open at the time of this update. Consider the Factor Game played as follows: Given a list of ...
3answers
781 views

### Hat 'trick': Can one of them guess right?

There are $n$ boys and $n$ girls. Each of them is given a hat of only 4 possible (known) colors and doesn't know its color. Now each can only see all the colors of hats of those of the other gender ...
2answers
459 views

### Game involving points on $[0,1]$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you ...
2answers
509 views

### A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
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 ...
2answers
545 views

### Is it true that we can get zero for all $(x,y,z)\in\mathbb{N}^3$?

There are three distinct positive integers $x$, $y$, and $z$. We can choose two numbers $a,b\in\{x,y,z\}$, where $b\leq a$, then replace $b$ by $2b$ and replace $a$ by $a-b$. Is it true that there ...
1answer
2k views

### Number of moves to solve a flood-it/sock-dye game

[ Question based on the sock dye game ] [ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ ...
4answers
2k views

### Reference for combinatorial game theory.

What is a good reference material for elementary combinatorial game theory? By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
2answers
600 views

### Make triangle of rods (game strategy)

There are set of rods of length $1,2,3,4 \dots N$. Two players take turns to chose 3 rods and compose triangle with non-zero area. After that this particular 3 rods are removed. If it is not possible ...
0answers
676 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 ...
2answers
6k views

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 ...
4answers
2k views

### Adding digits to make a number prime or composite

Players A and B alternate writing one digit to make a six-figure number. That means A writes digit $a$, B writes digit $b$, ... to make a number $\overline{abcdef}$. $a,b,c,d,e,f$ are distinct, \$a\...
3answers
6k views

### How many turns can a chess game take at maximum?

The shortest number of moves that a game of chess can have is 2, as far as I know: White moves pawn from f2 to f3, black moves ...
3answers
1k views

### Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
1answer
249 views

### Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields?

My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few ...