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.

Filter by
Sorted by
Tagged with
-1
votes
1answer
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] ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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,...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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{...
0
votes
0answers
26 views

Turning corners game

Hey I have to find winning move in turning corners game when position is: T H H T T T H T T T T T H T T T T T T T T T T H T T T T T H I know that SG function for this game is: $g(x,y)=\text{...
-1
votes
1answer
20 views

Sprague Grundy Function proof by induction

hey i have to find SG function for a subtraction game where we can take 1,3,4 chips. I found this function: $g(x)= \begin{cases} 0, x \equiv 0 (\mod7) \vee x\equiv 2(\mod 7) \\ 1, x \equiv 1 (\mod7) \...
2
votes
2answers
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, ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
18
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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$. ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
33 views

About vertex cut set

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 ...
2
votes
0answers
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 ...
-1
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
-2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
76 views

The adjacent number game.

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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
6
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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. ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
4answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
2
votes
0answers
79 views

5x5x5 Tic Tac Toe status

According to: http://library.msri.org/books/Book42/files/golomb.pdf from 2002, It is conjectured that in 5x5x5 Tic Tac Toe (standard rules), the second player ('O') can force a draw in a perfect play....
0
votes
1answer
22 views

Nash equilibrium for a normal-form game given by a poset

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

1
2 3 4 5
15