All Questions
Tagged with combinatorial-game-theory co.combinatorics
93 questions
69
votes
7
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
52
votes
4
answers
10k
views
Do there exist chess positions that require exponentially many moves to reach?
By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\...
- 82.7k
47
votes
3
answers
5k
views
Does knight behave like a king in his infinite odyssey?
The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle ...
46
votes
7
answers
10k
views
Conway's game of life for random initial position
What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...
- 24.7k
43
votes
4
answers
8k
views
Verifying the correctness of a Sudoku solution
A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...
- 16.2k
37
votes
2
answers
4k
views
Is there any superstable configuration in the game of life?
This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be stable-...
- 237k
31
votes
1
answer
1k
views
Vanishing line on Conway's game of life
If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
...
27
votes
4
answers
3k
views
Alice and Bob playing on a circle
I want to solve this problem:
Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move:
Alice takes one ...
- 379
26
votes
1
answer
2k
views
Who wins this two-player game based on the sandpile model?
Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an ...
- 1,743
25
votes
1
answer
1k
views
Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$
The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (...
- 32.5k
24
votes
6
answers
5k
views
Neutral tic tac toe
I heard this puzzle from Bob Koca. Suppose we play misere tic-tac-toe (a.k.a. noughts and crosses) where both players are X. Who wins?
That particular puzzle is easy to solve, but more generally, ...
- 82.7k
22
votes
4
answers
2k
views
The 1-step vanishing polyplets on Conway's game of life
A $n$-polyplet is a collection of $n$ cells on a grid which are orthogonally or diagonally connected.
The number of $n$-polyplets is given by the OEIS sequence A030222: $1, 2, 5, 22, 94, 524, 3031, \...
20
votes
1
answer
1k
views
A Ramsey avoidance game
Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...
- 3,004
19
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 48.9k
19
votes
3
answers
1k
views
The arithmetic progression game and its variations: can you find optimal play?
Consider the arithmetic progression game, a two-player game of
perfect information, in which the players take turns playing
natural numbers, or finite sets of natural numbers, all distinct,
and the ...
- 237k
18
votes
3
answers
666
views
Tic-tac-toe with one mark type
Parameters $a,b,c$ are given such that $c\leq\max(a,b)$. In an $a\times b$ board, two players take turns putting a mark on an empty square. Whoever gets $c$ consecutive marks horizontally, vertically, ...
- 1,209
17
votes
5
answers
4k
views
Nimber multiplication
Is there a game-theoretic interpretation of nimber multiplication? There is such for addition (a single move in a+b is either a move in a or a move in b).
- 281
17
votes
1
answer
2k
views
Mathematical solution for a two-player single-suit trick taking game?
The question on games and mathematics that appeared recently on mathoverflow
(Which popular games are the most mathematical?)
reminded me of a problem I encountered some time ago : starting with the ...
- 3,595
17
votes
3
answers
2k
views
Traversing the infinite square grid
Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark ...
- 171
16
votes
0
answers
988
views
A Combinatorial Game: the Snake and the Hunter
The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
- 3,717
15
votes
3
answers
2k
views
Why does the bitxor function appear in Nim?
I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...
- 1,129
14
votes
1
answer
607
views
Is there an elementary proof of a better result for the finite guessing-box puzzle?
The infinitary guessing-box puzzle is amazing — see here. In the basic form, the Guessing-box Hall has infinitely many wooden boxes, each containing a real number, and there are 100 mathematicians ...
- 237k
13
votes
1
answer
3k
views
The infinite X in Conway's game of life
In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...
user33772
13
votes
1
answer
799
views
Bipartite Nim-Geography
Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...
- 8,810
13
votes
0
answers
221
views
A game based on the Euclidean algorithm
The following game is based on a somewhat "stupid" version of the Euclidean algorithm (where we allow only subtractions).
Positions are given by finite non-empty multisets (repeated elements ...
- 17.9k
12
votes
1
answer
361
views
An averaging game on finite multisets of integers
The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of
integers. A move consists of choosing two elements
$a\neq b$ of $M$ of the same ...
- 50.8k
12
votes
1
answer
766
views
Sliding blocks puzzle
Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...
- 121
12
votes
0
answers
495
views
Connection properties of a single stone on an infinite Hex board
This includes a series of questions.
One of the most typical examples is shown as the picture below.
An half-infinite Hex board with an one row of black stones. Black stones are separated by one ...
- 661
11
votes
2
answers
402
views
Length of optimal play in Hex as a function of size
Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...
- 1,808
11
votes
2
answers
2k
views
Can anyone analyze this misere game?
Problem
Let $* = \{0\}$ be the one matchstick nim game, let $*2 = \{0,*\}$ be the two matchstick nim game, let $*3 = \{0,*,*2\} = *2+*$ be the three matchstick nim game, let $g = \{0, *2+*3, *2+*2+*2\...
- 8,810
10
votes
4
answers
2k
views
Has Sid Sackson's "Hold That Line" been analyzed?
In Sid Sackson's classic book A Gamut of Games, he introduces a game that he calls "Hold That Line." Briefly, it is an impartial pencil-and-paper game played on a finite grid of dots. The ...
- 82.7k
10
votes
0
answers
386
views
For which set $A$, Alice has a winning strategy?
Cross-posted from MSE: https://math.stackexchange.com/questions/4775193/for-which-set-a-alice-has-a-winning-strategy
Alice and Bob are playing a game. They take an integer $n>1$, and partition the ...
- 1,462
9
votes
3
answers
1k
views
The Sudoku game: Solver-Spoiler variation
Consider the Sudoku Solver-Spoiler game, a natural variation of the Sudoku game recently appearing in the question Who wins two-player Sudoku? posted by user PyRulez. In that game, the players attempt ...
- 237k
9
votes
1
answer
618
views
Erdős-Szekeres game
Given $n$. Two players in turn mark points on the plane. No three may be collinear, no $n$ may form a convex $n$-gon. The player who does not have legal move loses. Who has a winning strategy?
- 109k
9
votes
1
answer
389
views
Ordered Nim game
Consider the following variant of Nim:
There are two players and $n$ piles of stones, with sizes $a_1,\dots,a_n$, such that $a_i\leq a_j$ for any $i<j$.
A move consists of removing a positive ...
- 91
9
votes
1
answer
351
views
A Combinatorial Game with Integer Sequences
Two players, Alice and Bob, take turns constructing a sequence $a_1,a_2,a_3,\dots$, of distinct positive integers, none greater than a given parameter $K$. Alice plays first and makes $a_1=1$. ...
- 3,717
9
votes
1
answer
1k
views
A Game of Knights and Queens
Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such ...
- 27k
9
votes
1
answer
581
views
Is every ordinal the nimber of a ring?
This question is about the game of Noetherian rings, see MO/93276.
Here I will include the zero ring in order to get better formulas.
The nimber of a Noetherian ring is an ordinal number. It is ...
- 63.1k
9
votes
1
answer
460
views
Infinite-dimensional hex
Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...
- 777
8
votes
4
answers
2k
views
A "rewiring process" on graphs
I am interested in a discrete process defined as follows. We start with a given graph. At each time step we delete an edge $(i,j)$ and add two edges $e$ and $f$; the edge $e$ is incident with $i$ and ...
user3409
8
votes
1
answer
16k
views
Analysis of Misere Nim?
My friend likes to impress people by playing 3-5-7 which has three piles of counters of sizes 3, 5 and 7. You can remove any number of coins from a single pile, the last player to move loses.
ooo
...
- 22.8k
8
votes
1
answer
434
views
Yet another Erdős–Szekeres game
Given $n$. Two players in turn write different real numbers $x_1,x_2,x_3,\dots$
The player after whose turn there is a monotone subsequence of length $n$ loses.
I guess that the question 'who wins' ...
- 109k
8
votes
1
answer
433
views
Is "do-almost-nothing" ever winning on large CHOMP boards?
This is a special case of a question asked but unanswered at MSE:
Consider the combinatorial game CHOMP (presented as in the linked notes so that the "poison" square is bottom-left). In any $...
- 20.7k
8
votes
1
answer
230
views
Name of a game : Remove two chips from a vertex or one chip from both ends of an edge
Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a ...
- 17.9k
8
votes
2
answers
372
views
A game of singletons
Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:
Alice picks $m$ sets, each of which has $k$ items.
Bob colors some items in green.
Bob's score is the number ...
- 3,559
8
votes
0
answers
82
views
$2$-for-$2$ asymmetric Hex
This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers.
If the game of Hex is played on an asymmetric board (where the hexes are ...
- 181
7
votes
1
answer
207
views
Maximum $2$-D bootstrap percolation time for $n$ points on an $n\times n$ grid
I hesitate to ask this question here, but since it remained unanswered after a bounty on MSE, I ask it here with some reservation.
Is the maximum bootstrap percolation time for $n$ points on an $n\...
- 1,903
7
votes
1
answer
356
views
A Bitwise Xor Problem
Consider a sequence $a_i$ defined by
$$
\begin{align*}
a_1&=p,\\
a_2&=q,\\
a_i&=a_{i-1} \oplus a_{i-2}+1,
\end{align*}$$
where $\oplus$ is the bitwise xor operation. How can we give an ...
- 611
7
votes
0
answers
239
views
Chip firing on hypergraphs
A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...
- 20.7k
6
votes
1
answer
735
views
Bridge game with only one suit: strategy
This game looks like bridge, but 1- there are only two players Alice and Bob, 2- there is only one suit, whose cards are numbered $1, 2,\ldots,2n$. One deals each player $n$ cards. Therefore Alice ...
- 52.4k