All Questions
Tagged with combinatorial-game-theory recreational-mathematics
23 questions
35
votes
2
answers
5k
views
Who wins two player sudoku?
Let's say players take turns placing numbers 1-9 on a sudoku board. They must not create an invalid position (meaning that you can not have the same number in within a row, column, or box region). The ...
- 6,403
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
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
5
answers
3k
views
Irreversible chess
Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
- 223
21
votes
1
answer
825
views
Who wins the Rubik's cube game?
This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier).
Solver and Spoiler take turns making 90 degree twists (starting with Solver). ...
- 6,403
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
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
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
16
votes
2
answers
21k
views
Winning strategy at chomp (a chocolate bar game)?
The game of chomp is an example of a game with very simple rules, but no known winning strategy in general.
I copy the rules from Ivars Peterson's page:
Chomp starts with a rectangular array of ...
- 1,875
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
0
answers
205
views
Placing triangles around a central triangle: Optimal Strategy?
This question has gone for a while without an answer on MSE (despite a bounty that came and went) so I am now cross-posting it here, on MO, in the hope that someone may have an idea about how to ...
- 7,831
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
1
answer
1k
views
Game: Avoid the Gaussian primes
Here is a 2-player game played on a region of the
Gaussian integers, $\mathbb{Z}[i]$.
Initially four points are colored, opposite
corners of an $X$ by $Y$ rectangle:
$0 + 0i$ and $X + Yi$ are colored ...
- 151k
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
5
votes
1
answer
251
views
Monoid associated to $>2$-player Hackenbush
There is some literature on multiplayer combinatorial game theory, but as far as I can tell none of it follows the line of attack below. I'd love a pointer to a similar approach taken in the ...
- 20.7k
5
votes
0
answers
220
views
Is Domineering on any finite approximation of the Sierpinski Carpet always a second-player win?
The game of Domineering can be played on any board consisting of some subset of $\mathbb{Z} \times \mathbb{Z}$.
In particular, consider the boards $K_n$ generated by iterating the following inductive ...
- 3,393
4
votes
3
answers
1k
views
Generalized tic-tac-toe
We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first ...
- 82.7k
4
votes
1
answer
1k
views
Who wins this two player game of making squares?
Two players take turns coloring edges on an $n$-by-$n$ grid. Both players use the same color. Every time a player surrounds a square of the grid, they mark that square with their name and go again. ...
- 547
4
votes
0
answers
149
views
Combinatorial fairness property in division of goods
Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
- 388
2
votes
2
answers
320
views
How to describe the common boundaries between regions in a infinite Sudoku?
This relates to the answer to a question "Who wins two player sudoku?" and this awesome blog.
A Sudoku can be $N \times N$ where $\sqrt{N}$ is a natural number because $N \times N / \sqrt{N} \times \...
- 129
1
vote
0
answers
95
views
Eventual stabilization for repeatedly adding multiplayer games
This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.
To keep things readable, I'...
- 20.7k