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. For questions about traditional game theory, use the [game-theory] tag.
1,078 questions
2
votes
1
answer
227
views
Limit of mean duration of the game "Tug of Luck"
In the game "Tug of Luck" $n$ coins are tossed. Player A gets the tails and B gets the heads. Thereafter they take turns rolling a die until one player has gotten rid of all their coins and ...
- 644
0
votes
1
answer
96
views
Finding solution of a Sliding Puzzle of size $N \times N$.
We are given two matrices $R^{N \times N}$, each containing unique integers from $0$ to $N^2 - 1$ (except $0$, it does not need to be unique). The $0$ in the matrices will be called $blank$. The task ...
1
vote
1
answer
100
views
Misere Sprague-Grundy
In typical Sprague-Grundy, the person making the last move wins (the node with nimber 0 is losing). If we made it so the person who made the last move is losing - like in Misere Nim - what would be ...
- 113
0
votes
0
answers
80
views
Why is for surreal numbers $\frac{\omega}{2^m} = \left(\mathbb{N}, \left\{ \frac{\omega}{2^{m-1}}-n: n \in \mathbb{N} \right\}\right)$?
To prove that $ \left(\mathbb{N}, \left\{ \frac{\omega}{2^{m-1}}-n: n \in \mathbb{N} \right\}\right) = \frac{\omega}{2^m}$, one can try to show that $ \left(\mathbb{N}, \left\{ \frac{\omega}{2^{m-1}}-...
1
vote
1
answer
60
views
Unique Thermal Dissociations of Games - Combinatorial Game Theory
I have a question regarding the proof of Theorem 5.31 from Siegel's book "Combinatorial Game Theory".
Theorem 5.31. Every short game $G$ admits a unique Thermal dissociation.
Proof. Fix any ...
- 29
3
votes
1
answer
404
views
Best strategy to maximize number of tokens obtained
I was trying this problem from 2022 IIMC Keystage 3:
Anna and Boris play a game using a $6 \times 8$ board that contains one token on each unit square. Anna goes first, and they take alternating ...
- 1,113
0
votes
1
answer
72
views
Thermographs, Dyadic Temperatures, and Walls - Combinatorial Game Theory
I have a few questions about the proof of the following theorem (Theorem 5.10.) from Siegel's book "Combinatorial Game Theory" about walls and Left/Right scores. But first, for reference:
$...
- 29
0
votes
1
answer
75
views
Incentives on Integers Theorem - Combinatorial Game Theory
I am having some trouble understanding the proof of this theorem (Theorem 3.27) from Siegel's book, "Combinatorial Game Theory":
Theorem 3.27. If $G$ is not equal to an integer, then $G$ ...
- 29
9
votes
1
answer
277
views
Maximum Number of Liars that can Guarantee Finding a Truth-teller
The following problem was given at the 19-th All-Russian Mathematical Olympiad in 1993.
Thirty people from a company sit at a round table. Some of them are clever men
and some are jackasses. Each ...
- 410
0
votes
0
answers
58
views
Reversible Options - Combinatorial Game Theory
I have a few questions about reversible options and how they are bypassed.
Definition 2.3.
c) Let $G$ be a short game. A Left option $G^{L_1}$ is reversible (through $G^{{L_1}{R_1}}$) if $G^{{L_1}{...
- 29
7
votes
1
answer
366
views
What is the topology on the set of all plays of a game?
I read the wikipedia page on the "Angel Problem"(https://en.wikipedia.org/wiki/Angel_problem). It stated that there must be a winning strategy for either the angel or the devil because the &...
- 933
0
votes
1
answer
93
views
Infinitesimals and Unclear Induction - Combinatorial Game Theory
I am currently reading through Siegel's book on Combinatorial Game Theory, and have stumbled upon this theorem and its proof.
Theorem 4.2 (Lawnmower Theorem)
If $G$ is dicotic (all-small), $G$ is ...
- 29
0
votes
1
answer
174
views
1993 All-Russian Math Olympiad Regionals Grade 10 Problem 8
Here is the problem statement “From a square board $1000\times 1000$ four rectangles $2\times 994$ have been cut off as shown in the picture. Initially, on the marked square, there is a centaur - a ...
- 197
0
votes
1
answer
64
views
Incentives in Combinatorial Game Theory - Siegel
In Siegel's book on Combinatorial Game Theory, in the chapter on Short Games, there is a page on Incentives in said short games. But, after some trial and error, I noticed that Theorem 1.30 and it's ...
- 29
0
votes
1
answer
349
views
“Generalizing a coin-finding problem : Is m − 1 guesses always optimal for higher m?”
I participated in 2024 Simon Marais Mathematics Competition(SMMC),this problem was Q.1 in the paper-b ,I was not able to produce a rigorous solution for it in exam time .I really found this problem ...
