All Questions
Tagged with co.combinatorics combinatorial-game-theory
93 questions
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
14
votes
1
answer
608
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
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
4
votes
1
answer
432
views
"Infinity": A card game based on prime factorization and a question
I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
- 3,144
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 ...
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
2
votes
0
answers
67
views
How many ways to win a game between two teams with arbitrary player skills
Suppose we have $n\geq 4$ players $p_1,\cdots,p_n$ of a game between two teams: team $A$ and team $B$ (disjoint sets, each with two or more players, so that $|A|+|B|=n$). Assume that each player $p_i$ ...
- 167
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
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
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
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 ...
1
vote
1
answer
147
views
Name for an easy combinatorial game
What is the name of the following combinatorial game:
Two players, moving in turn.
Positions: $0,1,2,\ldots$.
Moves: $n\longmapsto n-1$ or $n\longmapsto \lfloor n/2\rfloor$
if $n>0$.
No move for $0$...
- 17.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
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
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, \...
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
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
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,838
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
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
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
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
1
vote
0
answers
256
views
The maximum number of moves in a game of Nim [closed]
I was assigned a fun, but also quite hard problem for my computer science class - I have to write a java program that computes the maximum number of turns in an optimal game of Nim.
In case you are ...
- 11
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
3
votes
2
answers
209
views
A "Markov game"
I call games similar to the one I describe below to be Markov games. I am selecting just that one or rather a 1-parameter series of games. The open challenge is to find out which of the players $\ 0\ $...
- 4,786
4
votes
3
answers
240
views
Best strategy for a combinatorial game
Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball.
Now suppose we are given 5 chances to pick 20 out of ...
- 281
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
3
votes
4
answers
2k
views
A chess question of W.T. Tutte [closed]
In "Graph theory as I have known it", p.12, Knights Errant, the late Tutte mentions as an aside the chess question "Does either Black or White have a certain win from the initial ...
- 313
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
5
votes
1
answer
6k
views
How many Tic Tac Toe games are possible? [closed]
Consider the average game of Tic Tac Toe or Noughts and Crosses. The game is played on a 3 by 3 two dimentional board. The game is played by two people and each person is allowed to only add one type ...
- 524
3
votes
0
answers
180
views
What values are representable by Hackenbush stalks?
It is known that every number can be represented by some red-blue Hackenbush stalk (see here, for instance). What values can be represented by red-blue-green Hackenbush stalks? In addition, what games ...
- 131
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
1
vote
0
answers
85
views
Winning criterion for a combinatorial game
Given $n$,
let $\mathcal{R}$ be a set of pairs $(\rho,A)$
where $A\subseteq n, \rho\in 2^A$.
Consider the following game between A and B.
At each round $t$, A enumerates an $m\in n$ (that has not been ...
- 909
1
vote
0
answers
136
views
Nim variant with minimum number of objects?
I'm wondering where I can find in the literature (if it exists) a discussion of a Nim variant where we impose the additional condition on Nim that we can remove only up to $c$ objects before the game ...
- 111
3
votes
1
answer
234
views
Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?
Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...
- 2,618
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$.
...
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
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
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
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
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
3
votes
1
answer
315
views
Difficulty of 3-color forest Hackenbush
"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...
- 32.5k
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
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
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,820
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
3
votes
2
answers
180
views
Satisfier-Falsifier games
In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...
- 3,559
6
votes
1
answer
173
views
What is the minimum worst-case length of an element removal game?
A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...
- 1,331
5
votes
1
answer
204
views
A set-family game
Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$).
Each ...
- 3,559
3
votes
5
answers
12k
views
How many possible ways are there to win in Quoridor? [closed]
Quoridor is a board game in which the objective is to move a piece across to the other side. A player can put up fences to block other players from advancing forward. How many possible ways are there ...
- 47