# 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.

743 questions
Filter by
Sorted by
Tagged with
23 views

### Game Theory(Breaking into Independent Games) [closed]

I have been solving a problem on Game theory but I am not able to proceed further. Problem Statement : Two persons(A and B) take turns playing a game. They are given N integers denoted by X[i] ...
14 views

### Nilpotent short games of odd order

Is there a short game $G \ne 0$ such that $G + G + G = 0$? It seems to me like such a game shouldn't exist, but I am unable to prove it. Can anyone give an example of such a game, or a proof that one ...
38 views

### Is there a construction of surreal games that isn't related to actual games?

Is there a way to construct games that isn't based on games? For example, construction of the surreal numbers. I haven't seen anything about Dedekind cuts that allow for the lower set to be larger ...
24 views

### Ulam‘s Liar Game changing number

I did some research on Ulams Liar game where person A thinks of a number between 1 and 1 Million and person B asks Yes/No questions. If person A is allowed to lie once, person B needs 25 questions to ...
38 views

### The game of taking an even number of stones

Consider the following game: Two players alternately take one or two stones from a pile of stones. The objective of each player is to take, in total, an even number of stones. Suppose that in the ...
63 views

### Do surreal gaps have birthdays?

Do gaps like $\infty$ & on have birthdays? I haven't ever seen anywhere that they do, & I think the answer is that they don't (although I'm not sure how to prove it). This got me wondering,...
97 views

### Is $\frac{1}{+_{on}}$ the largest game?

On page 297 of Combinatorial Game Theory by Aaron Siegel it is stated that: $+_{on}=\{0||0|\text{off}\}$ [is] the smallest positive game of all. In More Infinite Games by John H. Conway the ...
17 views

### Progress in thermographic & atomic weight calculi for combinatorial games

In Combinatorial Game Theory by Aaron Siegel the following are given: Question (page 150). Can the atomic weight theory be generalized to higher-order uptimals? Open Problem (page 151). Extend ...
45 views

### What's the deal with ace & pip?

In Combinatorial Game Theory by Aaron Siegel on page 298 the games ace, deuce & trey are introduced: $$\text{ace}=\{0|+_\text{on}\}$$ $$\text{deuce}=\{0|\text{ace}\}$$ \text{trey}=\{0|\text{...
26 views

60 views

### What is the relationship between surreal star and the empty set?

In Surreal Numbers and Games on page 6 it says that $0=\{\emptyset|\emptyset\}$. Additionally, on page 10 it says that $*+*=0$ and that for any value $x$ we have $x+*=\{x|x\}$. Given the previous, ...
67 views

### how to calculate $25\otimes 40$ [duplicate]

Hey i need to do nim multiplication of numbers: a) 6 ⊗ 24 b)25 ⊗ 40 I starded with a) and calculate that $6\otimes 24= 96\oplus(6\otimes 8)$ and I dont know how to calculate this to the end. In point ...
35 views

### 5-color coloring game.

Lets say there are 2 players, A and B. Lets say we have map. The game is played this way, Player A picks a region, PLayer B colours it in such that the region is a different colour to all adjacent ...
230 views

### How does Conway's proposed compromise for constructing the real numbers actually work?

My question is about understanding a remark John Conway made in On Numbers and Games (ONAG), where he proposes a method for constructing the real numbers from the rationals. I will have to assume ...
36 views

### Does Sprague-Grundy help solve any impartial games that don't comprise independent sub-games?

By "solve" I mean efficiently compute whether a given position is a $\mathcal{P}$-position (first-player win). By "efficiently" I mean compared with "brute force", which involves recursively labeling ...
35 views

### Is there a combinatorial game which is incomparable with 0 and every order 2 game?

I've recently been playing around with combinatorial games and I came across what I've been calling halves of games. In particular, if $G$ is a game then a game $x$ is a half of $G$ if $x+x=G$. ...
55 views

### What exactly is surreal star? What does it mean that it is incomparable to zero?

I have been thinking about this for a while & I am perplexed. What exactly is surreal star? I am aware that it is a fuzzy game. What I don't understand is what exactly that means. Wikipedia says ...
71 views

### Possibility of ants not being able to cross a grid shaped bridge

The problem is really simple, but I have absolutely no idea on how to solve it. So there is an ant who really wants to get to the other side of a grid shaped bridge. However, a person decides to stop ...
33 views

Suppose there is an undirected, connected graph $G=(V,E)$. Let $U\subseteq V$. Define vertex-deletion subgraph $G−U$ as the graph obtained from $G$ by deleting from $G$ the vertices in $U$ and ...
39 views

### Is the circle packing game equivalent to the circle packing problem?

I came up with the following impartial combinatorial game. The game starts with an empty square with a given side length. The two players take turns, and in their turn, they place a circle of radius ...
71 views

### Understanding Nim

I was going through a problem where we have given $k$ piles from $1$ to $k$ and each pile contains some stones. Now, there is a game in which there are $2$ players, say $A$ and $B$ who removes stones ...
27 views

### Winning strategy to a Nim-variant game

Given the following variant to the game of Nim: The game begins with n-heaps of m-stones each. The player, every turn, must ...
61 views

### Dynamic subtraction game with function

Let's start with rules of the game: There is one pile of n chips. The first player to move may remove as many chips as desired, at least one chip but not the whole pile. Thereafter, the players ...
72 views

### Fibonacci nim winning strategies in different situations

Rules of fibonacci nim: Fibonacci nim is played by two players, who alternate removing coins or other counters from a pile. On the first move, a player is not allowed to take all of the coins, and ...
46 views

### Two players are playing a game [closed]

Bob and alice are playing a game: There are 1999 balls. The players take turns to remove some of the balls (Bob first), the only restriction one has to take at least one ball and at most half of the ...
64 views

### SOS game with $n=14$ and $n=2000$

The board consists of a row of $n$ squares, initially empty. Players take turns selecting an empty square and writing either an S or O in it. The player who first succeeds in completing SOS in ...
53 views

### Nimble game and NIm game

Exercise: Rules of Nimble game: Nimble game is played on a game board consisting of a line of squares labelled: 0,1,2,3,.... A finite number of coins is placed on the squares with possibly more than ...
76 views

Preface: Four years ago, when I was in Grade 6 and in the Hanoi team training for the International Math Tournament of the Towns (IMTT), the leader of the Vietnam IMO team came and first provided me ...
82 views

### A game of tourism

CONTEXT Currently I am reading a series of book by Martin Gardner, the one I am working on is "The colossal book of Mathematics". Knowing that this man is hail as the greatest Math-Magician of the ...
31 views

### How many ways are possible to win this game for the first player in first turn?

A 2-player game : Given a sequence of integers, in each move, a player can select few numbers of same value and discard them from the sequence . They play their moves alternately. Player-1 plays ...
361 views

### The spreading game and its expansion

For all those who lost their lives and due to this tragic disease CONTEXT This question is inspired by the following question that was proposed by my math teacher Lam Nguyen, I shall cite this ...
42 views

### How do I show that is G has no right options, then there exists an n $\in$ $\Bbb Z$, where $G = n$

I know that if $A+B+C=0 \to a+b+c=0$, and by extrapolating I can get $A+B=C \to a+b=c$, and I know that it will have to be an inductive proof, but I'm not sure how to phrase the proof. I'm assuming ...
135 views

### How many possible orders can the first Los Santos missions of GTA: San Andreas be completed in?

This is actually a pretty interesting combinatorics problem, as there's several different branches in the mission tree that split off and join together, and of course there are prerequisites for each ...
63 views

### Is a version of The Angel Game with a stronger Devil viable?

I cannot find research on a $\beta$-Devil version of The Angel Game. I am not sure if I cannot find it because I am not able to research it properly or if there is not much theory on this. In case ...
34 views

### Winning strategy for removing coins from coin piles of size 2020 and 2021

Suppose that two players A and B are playing a game on two piles of coins of size 2020 and 2021. There are two actions available: Remove one coin from each pile. Remove two coins from any one pile. ...
29 views

### Basic definition for beginners and usage of Parity of a permutation

I am interested to know from basic to advance what is PARITY of a permutation I have searched about it but each time I got more confused. I want to know the logic behind parity, like why is it ...
53 views

### What area of mathematics would the “24 game” encompass? [closed]

I'm doing an investigation on the 24 game and it's general solutions. However, as I'm still in high school, I don't know where to begin searching. Since the game deals with integers and how they can ...
38 views

### Are chess PSPACE-complete or PSPACE-hard only?

There are links that claim that chess are PSPACE-complete but the snippet below from the Handbook of theoretical computer science says that they are harder. Which statement is true ?? EDIT: included ...
201 views

### Proof by Induction: Chocolate Bar Question [duplicate]

A chocolate bar is divided into an m x n grid and one of the corner pieces is poisoned. In the chocolate bar game, two players take turns alternately dividing the chocolate into two pieces and ...
87 views

### Misere nim game - winning move for player 1

A misère version of the nim game is being played. Let there be 4 piles of coins, each having 17, 25, 55, 60 coins respectively. What is the winning move for player 1? I figured out the normal version ...
30 views

### Game on a graph Hall’s marriage theorem

Let $G$ by a bipartite graph with parts $X,Y$ both of size $n$. Two players alternately name vertices. P1 names a vertex $a_1$ in X. Then P2 names a vertex $b_1$ in Y which has an edge to $a_1$. Then ...
50 views

### Subtraction Game with Two Piles of Stones

In this subtraction game, there are two piles of stones, and a player can take between 1 and 4 stones from the first pile or between 1 and 5 from the second. I am trying to determine which positions ...
101 views

### Counting to 100 game with a twist (A Nim Variation?)

So the premise is the classic two-player counting to 100 game: players alternate picking an integer between 1 and 10 (inclusive), and the first to let the cumulative sum be greater than or equal to ...
33 views

### Win Conditions for Single Pile NIM (players can only take a or b stones from the pile on each turn)

Two players alternate turns taking either $a$ or $b$ stones from a pile of $n$ stones. The first player who cannot move loses. Player 1 is the player who goes first and Player 2 is the player who goes ...
86 views

### Game of coins - find the winning strategy

Alice and Bob play a game. There is a box with $n \geq 2$ coins in it. Bob starts first and he can take any amount of coins from the box and put them on the table, but not all of them. Then, Alice can ...
38 views

### Calculate all possible combinations of symmetries on a 10x10 square grid

I would like to calculate all possible combinations of symmetries, that a $10\times 10$ board of Dots and Boxes can have. For this purpose we only care about what lines have been drawn, but not which ...
57 views

### Conway games and Induction Principle for games

First of all, about the Notation: Conwaygame: Let x,y be sets containing Conwaygames, then the ordered tuple G:=(x,y) is a Conway game. Call the elements of x (the elements of y) the left options of ...
Let $P$ be a poset partially ordered set. EDIT: $<$ is antisymmetric but not necessary associative. Hence, $(P,<)$ is not necessarily a poset, as reminded me by joriki. Consider a simple $2$-...