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.

Filter by
Sorted by
Tagged with
349
votes
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 ...
58
votes
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 ...
49
votes
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 ...
47
votes
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 ...
42
votes
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, ...
37
votes
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 ...
34
votes
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 ...
32
votes
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 ...
31
votes
1answer
802 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 ...
28
votes
1answer
656 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.)...
26
votes
3answers
830 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 ...
25
votes
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 ...
20
votes
2answers
465 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 ...
20
votes
2answers
528 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 ...
19
votes
0answers
693 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 ...
18
votes
2answers
548 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 ...
18
votes
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)$ ...
17
votes
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 ...
17
votes
2answers
612 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 ...
17
votes
2answers
7k views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
17
votes
0answers
694 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 ...
15
votes
3answers
4k views

Average Scrabble graph structure: diameter?

Tonight a game of Scrabble ended in what I consider a very unusual graph structure, unlike this generic web image, which seems more typical:           ...
15
votes
5answers
965 views

A Knight and Knave Problem

There are $69$ people in a room, of which $42$ are truth-tellers (they always tell the truth) and the rest are liars (they can lie or tell the truth). You are allowed to ask any person $A$ whether any ...
15
votes
1answer
1k views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...
14
votes
2answers
330 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
14
votes
4answers
396 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 or n] ...
13
votes
1answer
3k views

Bidding Tic Tac Toe

In regular tic tac toe, both the players get alternate chances. This is a variant of that. Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$. Both ...
13
votes
2answers
454 views

Game for mathematicians about differentiation of polynomials and subtractions in their coefficients.

I'm in a french puzzle forum and one of us asked this puzzle Game of polynoms. We are having some difficulties solving it for the first case. And we have not begun to think about the generalisation, ...
13
votes
1answer
2k views

Determinant game - winning strategy [duplicate]

I came across this problem while looking at Putnam problems a while ago: Alan and Barbara play a game in which they take turns filling entries of an initially empty $2008 \times 2008$ array. Alan ...
13
votes
1answer
383 views

Who has a winning strategy in the hamilton-circle-game?

The game starts with a graph with $n$ vertices and no edges. The players alternately add edges until the graph contains a hamilton-circle. The player who made the last move loses. Who has a winning ...
13
votes
1answer
631 views

Create the most 'stressful' tennis game ever!

Some sports, such as tennis, use a complicated points system (point, game, set, match; with deuces and tie-breaks) for what would otherwise be an extremely simple and monotonous sport. The main reason,...
13
votes
0answers
385 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 ...
12
votes
3answers
2k views

An invisible ghost jumping on a regular hexagon

Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i....
12
votes
5answers
2k views

Does a finite game that cannot be drawn imply a winning strategy exists?

The author of this page, about a simple game (Chomp) http://plus.maths.org/content/mathematical-mysteries-chomp makes the following statement: "One of the players is sure to have a winning strategy. ...
12
votes
2answers
1k views

board game: 10 by 10 light bulbs, minimum switches to get all off?

Hy all! My problem is as follows: There's a board of 10 by 10 light bulbs. (So it's a square with 10 columns and 10 rows.) Every single bulb has got its own switch. However, something went wrong and ...
12
votes
2answers
1k views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
12
votes
3answers
230 views

Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected). Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such ...
12
votes
1answer
247 views

What's known about this combinatorial game?

Two players play a game as follows. There is a line of $n>3$ spaces, initially empty. The players take alternate turns. On each turn, the turn player puts a stone onto an empty space. If, as a ...
12
votes
1answer
2k views

Solving Chess - alternatives to brute force

It is well known that solving Chess is practically impossible using brute force methods. I'm interested to know if there have been any serious attempts using alternate methods. What theory and ...
12
votes
2answers
225 views

Graph theory partitioning game

Players Ruby and Bob are given an undirected graph and a number $N$. First Ruby colors $N$ vertices red, then Bob colors $N$ vertices blue (they must be distinct from Ruby's choices). Afterward, all ...
12
votes
1answer
205 views

Are there infinitely many $\alpha \times \beta$ Chomp boards where player 2 wins?

Let $\alpha$ and $\beta$ be nonzero ordinals. Infinite chomp (called ordinal chomp by Wikipedia) on an $\alpha \times \beta$ board is played as follows. We consider the set $\alpha \times \beta$, ...
11
votes
5answers
1k views

Big List of examples of recreational finite unbounded games

What are some examples of mathematical games that can take an unbounded amount of time (a.k.a. there are starting positions such that for any number $n$, there is a line of play taking $>n$ times) ...
11
votes
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 ...
11
votes
2answers
754 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
11
votes
1answer
284 views

Prove that $5 \times 5 \times 5$ tic-tac-toe ends in a draw

I am pretty sure that when played perfectly, $5 \times 5 \times 5$ tic-tac-toe will end in a draw. Is anyone able to prove this?
11
votes
2answers
2k views

Breaking chocolate bars game

About two weeks ago, a friend of mine taught me the following game without his knowing the answer. It may be famous, but I haven't known it. There are $N\ (\in\mathbb N)$ chocolate bars composed of $...
11
votes
0answers
354 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 ...
10
votes
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\...
10
votes
3answers
7k 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 ...
10
votes
1answer
262 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 ...