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.

learn more… | top users | synonyms

135
votes
0answers
4k views

The Ring Game on $K[x,y,z]$

I recently read about the Ring Game on Mathoverflow, and have been trying to determine winning strategies for each player on various rings. The game has two players and begins with a commutative ...
12
votes
0answers
410 views

“Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
11
votes
0answers
383 views

Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple. Disconnect. Players alternately remove vertices from a ...
8
votes
0answers
124 views

NIM with multiple winning final positions

I've been looking at a variant of NIM. You can skip this bit where I'll describe NIM as usually described: There's a starting position with some number of piles of counters and two players ...
6
votes
0answers
72 views

Has this subset-sum game been studied?

Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their ...
5
votes
0answers
329 views

Chat Noir solvable?

There is a relatively simple flash game that I enjoy playing -- http://www.gamedesign.jp/flash/chatnoir/chatnoir.html is one version of it, though I've found many -- and it centers around trying to ...
4
votes
0answers
56 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...
4
votes
0answers
49 views

Prime number building game

Players $A$ and $B$ choose digits $(0, \dots , 9)$ turn by turn and build number by concatenating the digit they chose to the end of the number. Player $A$ starts by picking the first (one-digit) ...
4
votes
0answers
37 views

The point-open game and $\omega$-covers

Let $X$ be a topological space. The point-open game $G_{po}(X)$ is defined as folows. It is played by two players ONE and TWO. In the n'th step $(n \in \omega)$, ONE choose a finite subset $F$ of ...
4
votes
0answers
66 views

Nimber of selective compound games

Background/Definitions. Let $\alpha,\beta$ ordinal numbers. The Hessenberg sum $\alpha \# \beta$ is defined recursively as the smallest ordinal which is $>\alpha' \# \beta$ and $> \alpha \# ...
4
votes
0answers
89 views

Linear Independence Game

Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
4
votes
0answers
183 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
4
votes
0answers
124 views

Number Theoretic Game

2 players A and B play a game. At the start of the game, $n$ positive integers (not necessarily distinct) are written on a notebook. First, player A chooses a number from the notebook and declares it ...
4
votes
0answers
937 views

How many different chess-board situations can occur?

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist? Upper bound: Well, you have 16+16 = 32 chess pieces ...
3
votes
0answers
31 views

on a game playable with tokens

Here is a two-player game playable with tokens. At the beginning, all tokens form a single heap. Players must choose among all heaps one of them and cut it in two parts, so that all heaps have ...
3
votes
0answers
74 views

News on SG values of Grundy's Game?

Is there any recent research into the Sprague-Grundy values of Grundy's game? It was calculated to $2^{35}$ integers but with no sight of recurrence. Has anyone come up with anything new to compute ...
3
votes
0answers
56 views

How many different Forsyth-Edwards Notation ranks are possible?

(This is a combinatorics question, and therefore more appropriate here than at the Chess Stack Exchange.) Background: in chess, board positions are recorded using a system called Forsyth-Edwards ...
3
votes
0answers
66 views

Terminology questions about a game where one may “save his progress” at the cost of a turn.

The game is for $p$ players who each start at square $1$. Each turn, a player can either roll an $m$-sided dice or place a marker on his current square. If he rolls $x\in\{2,\ldots, m\}$, he ...
2
votes
0answers
203 views

stable marriage algorithm problem

Better of the two Suppose that in the stable marriage problem with $n$ men and $n$ women, we have found two (possibly different) stable matchings $S$ and $T$. We will show how to combine $S$ and $T$ ...
2
votes
0answers
96 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
2
votes
0answers
43 views

Computation of a 3-dimensional game matrix

For natural numbers $n_1 \leq n_2 \leq n_3$ we define $\beta(n_1,n_2,n_3)$ recursively to be the smallest natural number which is not among the numbers $\beta(m_1,m_2,m_3)$, where $m_1 \leq n_1 \leq ...
2
votes
0answers
461 views

What is the highest possible score in 2048 hard?

There is a variant of the popular game 2048, called 2048 hard or 2048 impossible, which automatically places each new tile in the hardest possible location. Is this variation possible to solve, and if ...
2
votes
0answers
143 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
2
votes
0answers
117 views

The name of a game from the 2013 Putnam

Does the following game from the 2013 Putnam have an official name? Based on my searches, it seems to have been created just for the exam. Let $n\geq 1$ be an odd integer. Alice and Bob play the ...
2
votes
0answers
204 views

Stable Marriage Problem

I would just like clarification for the following problem: Suppose $M_1$ and $M_2$ are two stable matchings between n men and n women, and we allow each woman to choose between the man she is paired ...
2
votes
0answers
235 views

What are the chances of shooting the moon in Hearts?

I'm posting this again here from boardgames.SE because it was suggested there that this is the more appropriate question to ask it. So, that said, here's my question: given a fair shuffle, that all ...
2
votes
0answers
117 views

Unavoidable structure of this kind of function:$Z\rightarrow N$.

Suppose that $f$:$Z\rightarrow N$ is a surjection and $|f^{-1}(n)|=2$ for every $n\in N$. I found that there is $n\in Z$ such that $f(n)$, $f(n+1)$, $f(n+4)$, and $f(n+5)$ differ from each other. ...
1
vote
0answers
24 views

Multi-dimensional naughts and crosses: victory for first player?

In a $2$-dimensional checkerboard which is $2\times2$, the player going first necessarily achieves $2$ in a row. In a $3$-dimensional board which is $3\times3\times3$, a player going first using a ...
1
vote
0answers
33 views

How is Wythoff's Theorem proved?

Specifically, how does one prove the following? Suppose $(a,b)$ is not of the form $(A_n,B_n)$, where $A_n=\lfloor n \phi \rfloor$ and $B_n= \lfloor n \phi^2 \rfloor$. Then there is a move in ...
1
vote
0answers
201 views

Create the most 'stressful' tennis game ever!

Some games, such as tennis, use a complicated points system (point, game, set, match; with deuces and tie-breaks) for what would otherwise be an extremely simple and monotonous game. The main reason, ...
1
vote
0answers
77 views

Counting all possible legal board states in Quoridor

Ignoring pawns there are 1,375,968,129,062,134,174,771 possible ways to place 0 to 20 walls on the Quoridor board, as answered here. Ignoring walls there are 81 * 81 = 6410 ways to place the two ...
1
vote
0answers
78 views

Distribute the gold, silver and bronze

A pirate ship has 2015 treasure chests (all chests are closed). Each chest contains some amount of gold, some amount of silver and some amount of bronze. To distribute the gold, silver and bronze the ...
1
vote
0answers
74 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
0answers
43 views

What is the optimal strategy?

There are $m+n+1$ cards numbered $1,2,\ldots m+n+1$. Participants A and B respectively get $m$ and $n$ cards. Meanwhile, they only know what they get. The remaining card is face down on the desk. ...
1
vote
0answers
53 views

How many lines needed to not lose in tetris game?

Suppose we play a tetris game with tetris be given randomly. Is there exists a number of lines that we can play infinitely, i.e. do not lose the game?
1
vote
0answers
31 views

Does any $\omega$-cover in which $X \in L(\mathcal U)$ is also a $\gamma$-cover?

As a continuation to this question: An $\omega$-cover, is an open cover $\mathcal U$ of $X$, such that, $X \notin \mathcal U$, and for every finite set $F \subset X$, there exists an open set $U ...
1
vote
0answers
233 views

Proof that $12$ in a row tic-tac-toe is a tie game?

How can be it proved that tic-tac-toe on an infinite grid (winning with $12$ in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)? There is a hint: to ...
1
vote
0answers
61 views

Any known strategies for toads and frogs?

Are there any heuristic strategic for playing Toads and Frogs known? I reckon the optimal playthrough may be hard to achieve due to the game being NP-hard but at least something that regularly ...
1
vote
0answers
45 views

What are the available libraries or programs for finding extremes of a function with no symbolic definition?

In my current mathematical inquiry, I would like to gain insight on behaviour of a $d$-dimensional continuous function by locating its maximum over the hyperplane $\sum_{i=1}^d x_i = 1$ for $x_i$ ...
1
vote
0answers
117 views

More than Nim (combinatorics problem)

A two-player game is played with two piles of stones, with sizes m,n. On a player's turn, that player can remove any positive number of stones from one pile, or the same positive number of stones from ...
1
vote
0answers
196 views

S-Grundy Number

Help needed in understanding S-Grundy Number , any good tutorial. I am trying to solve Mathalon Problem 146 S-Grundy Game
0
votes
0answers
14 views

Is this general variant of nim NP-hard to decide who has a winning strategy?

Suppose there are $n$ piles of stones, where pile $i$ originally has $m_i$ stones, and each pile has a maximum number of stones $k_i$ that can be taken on each turn. Fix integer $N \geq 1$. Suppose ...
0
votes
0answers
18 views

super-additive, sub-additive, and shapely value limitations?

I am working on the coalition formation. Most of the scientist used concept of shapely value for distributing the utility among the members of coalition. Up to my understanding, shapely value is good ...
0
votes
0answers
38 views

Solving a Recurrence for a Mathematical Game

The problem is: Two players take turns removing coins from a pile. There are initially $n$ coins, and on each turn, a player can remove $a_1, a_2, \dotsc, a_k$ coins. The player who cannot remove ...
0
votes
0answers
80 views

How many ways we can arrange numbers such that sum of arrangement will be a given number

we have a value $p$ and we have to arrange numbers at $p$ places such that no number is greater that $p$ and no number is less than $0$ and also sum of arrangement should be a given number (suppose ...
0
votes
0answers
168 views

Stable Marriage Algorithm Doubt

Please give me more insight on these questions and correct them if they are wrong. (True/False) In a stable marriage algorithm execution which takes n days, there is a woman who did not receive a ...
0
votes
0answers
48 views

Combinatorial approach to calculate determinant

Suppose you have set of $n*n$ matrices with entries from the set $\{1,-1\}$. Then what can be the maximum determinant which you can obtain from such type of matrices.
0
votes
0answers
16 views

Linearization bounds on 0-1 quadratic problems

What are the best linearization methods for approximating the following constrained 0-1 Quadratic problem, where $Q \in \mathbb{R}^{n\times n}$ and $k$ is an integer $1\leq k \leq n$ $$ \max ...
0
votes
0answers
12 views

Combinatorics- related to poker

In how many ways can a straight flush be dealt ,if two of the cards originally dealt must be discarded and replaced but not if all the 5 cards are clubs ?
0
votes
0answers
34 views

Number of ways to shuffle a cardset with fixed top 4 while ignoring the suit

I am interested in the number of possible orders in a standard 52 card deck. There are $52!$ possible orders, if I care for suit and type. If I don't care for the suit / color of the card there are ...