Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

340
votes
0answers
13k 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 ...
19
votes
0answers
667 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 ...
17
votes
0answers
677 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 ...
13
votes
0answers
361 views

Strategy for board game 2

In this question the following was asked: Alice and Bob are playing the following game: They have a $4 \times 4$ empty grid and take turns coloring one square each, starting with Alice, both using ...
11
votes
0answers
346 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 ...
7
votes
0answers
141 views

Broken stick game

Two players Alice and Bob play the following game consisting of $n-1$ turns. Initially the segment $[0,1]$ is given. Alice and Bob then alternate breaking one segment into two pieces. After all turns ...
7
votes
0answers
155 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 ...
7
votes
0answers
282 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) ...
7
votes
0answers
867 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 ...
6
votes
0answers
231 views

British Maths Olympiad (BMO) 2004 Round 1 Question 4 alternative solutions?

The question states: Alice and Barbara play a game with a pack of $2n$ cards. On each of which is written a positive integer. The pack is laid out in a row, with the numbers facing upwards. Alice ...
5
votes
0answers
61 views

Question about proportion of Nim positions

Let a Nim game be represented by a sequence of positive integers. We call a Nim of size $n$ when the sum of its elements is $n$. Let $a(n)$ be the number of Nim games of size $2n$ with Nim sum 0. ...
5
votes
0answers
106 views

Improper integrals over the reals and surreal numbers

Is it possible to assign improper integrals over the reals a surreal value in a consistent way? Are there any papers available on this? Note that I am not inquiring about formalizing integration over ...
5
votes
0answers
95 views

Reference Request: A Tychonoff space $X$ where the game $\mathrm{G}_1(\Omega,\Omega)$ is undetermined

Given a Tychonoff space $X$, let $\Omega$ be the set of all $\omega$-coverings of $X$, where by $\omega$-cover we mean a collection $\mathcal{U}$ of open sets of $X$ such that for any $F\in[X]^{<\...
5
votes
0answers
142 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 ...
5
votes
0answers
118 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
84 views

Betting on intervals

Assume we have $n$ white points on a line, and that at a certain time a random subset of those points turns black. We have two teams A and B consisting of a finite number of players each of which is ...
4
votes
0answers
82 views

Which subsets of the real numbers can you play Sylver coinage on?

For a set $S$ of real numbers, we say that you can play sylver's coinage on it if for any infinite sequence of $x_n \in \mathbb R$, there is some $N$ such that $x_N$ is a sum of previous terms. For ...
4
votes
0answers
86 views

Ballot problem with initial votes counted

In an election where candidate $A$ receives $p$ votes and candidate $B$ receives $q$ votes with $p > q$, what is the probability that $A$ will be strictly ahead of $B$ throughout the count given ...
4
votes
0answers
156 views

n-Meta tic tac toe strategy

We all know how 1-Meta tic tac toe works-standard tic tac toe. 2-Meta tic tac toe works by placing tic tac toe grids in a tic tac toe grid. Players can go in any grid at any time, and the player who ...
4
votes
0answers
194 views

Choosing the intervals

The game consist of two sequences of integers A of length N and B of length M, and it will last for exactly M turns. In the i-...
4
votes
0answers
852 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 ...
4
votes
0answers
79 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 $X$, ...
4
votes
0answers
113 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 ...
4
votes
0answers
90 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
275 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
172 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 ...
3
votes
0answers
57 views

Solving the Matrix Game

Let $\{v_j\}_j$ be a collection of $n$ column vectors $v_j \in \mathbb{F}_2^{r}$ s.t. the matrix built from those has no zero rows. Now we play a game: You have 3 options: You may drop any column ...
3
votes
0answers
142 views

Andrew and Ben play on graph

Given complete graph with $n$ vertices. Andrew in his turn removes exactly one edge and Ben in his turn removes two or three edges. They take turns one after another and Andrew begins. The player ...
3
votes
0answers
71 views

Who has a winning strategy for a finite number of moves, the first or the second player?

Two players play the next game: They start with the polynomial $$2013x^2+2012x+2011$$and play by turns. Each player in his turn subtracts from the current polynomial one of the following polynomials: $...
3
votes
0answers
56 views

Let $n<\sqrt{5\cdot2^{11}}$, and say we have a 2 colouring on ${1,2,…,n}$.

Let $n<\sqrt{5\cdot2^{11}}$, and say we have a 2 colouring on ${1,2,...,n}$. Prove that there exists an arithmetic progression of length 10 that isn't monochromatic. This was given to us in an ...
3
votes
0answers
197 views

Can this game end in a draw?

We have this game: Clarifications: Pawns can move and take across sides. Pawns can't jump over other pieces when moving by two squares. "Forward" means from the middle of your side towards the ...
3
votes
0answers
35 views

Finitely many steps to $n$-stone pile.

I have a combinatoric problem still unsolved: $2n$ ($n$ is a positive integer) stones are divided into $3$ piles. In each step, we pick half of a pile which has even number of stones and move those ...
3
votes
0answers
136 views

Mathematical game with numbers

We invented a mathematical game, which i am going to explain here. The first player choose a natural number, lets call it $n$ (if you play it for real, you must choose a sufficiently big number so ...
3
votes
0answers
211 views

Candy Crush as an integer programming problem

I'm trying to model the basic version of a match-three game, where the player (has a maximum number of swaps) must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match ...
3
votes
0answers
745 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$ ...
3
votes
0answers
99 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
70 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
43 views

Games and Dyadic Rationals

Suppose $a$, $b$, and $c$ are dyadic rationals, where their corresponding numbers (games) are $A$, $B$, and $C$ respectively. Prove that $a+b=c$ if and only if $A+B\sim C$ (or $A+B$ is equivalent to $...
2
votes
0answers
32 views

The smallest-sum game

The game is a function of an integer $n\geq 1$ and a number $t\in(0,n)$. An adversary picks $n$ numbers in $[0,1]$ whose total sum is $t$. You divide the numbers into two subsets and the adversary ...
2
votes
0answers
20 views

A simple game with $n$ points in 3D space - red triangle wins

(Once again a son is torturing his father...) Alice and Bob play a fairly simple game with $n$ predefined points in 3D space. No four points are complanar (which also implies that no three points are ...
2
votes
0answers
80 views

King of the Centre - Is this an existing game?

Consider an $n$-player infinitely repeated game. First stage nature chooses for each player, $i$, a radius $r_{i}$. For each later stage $t$ each player $i$: The payer chooses a "target" $p_{i, t}$...
2
votes
0answers
68 views

Queens on a torus chessboard.

Consider a Torus chessboard $\mathbb T$ of dimension $8\times8 $. How much queens it is possible to put on in such a way that no one attacks another? (I assume we use the same rules of standard ...
2
votes
0answers
91 views

Math problem from logical game

We have a set of arrows and can start from any point. Every next point must be chosen in direction of previous and can be used only one time. We need to visit all points. Direction of last point doesn'...
2
votes
0answers
52 views

Given a linear path with $n$ dots connected by $n-1$ lines, find the minimum number of coins required to win the game

Given a linear path with $n$ dots connected by $n-1$ lines, find the minimum number of coins required to win the game provided the game features are as follows: In the following game, you're given a ...
2
votes
0answers
224 views

Game on triples of integers modulo 3n

Consider the following game played on triples of integers modulo $3n$. Player $B$ writes down the triple $(a,a+n,a+2n)$. Starting with player $A$, they then take it in turns to add $1$ to one of the ...
2
votes
0answers
244 views

Distributed Assignment Problem for resource allocation

I am working on a resource allocation problem, which is formulated as an 'assignment problem'. It is solved using Hungarian Method. Let's assume that below is my assignment problem, where each ...
2
votes
0answers
124 views

Universal algorithm to win a turn-based math game

One of my friends suggested me to play a game. It is a turn-based math game that requires 2 players. Here are the rules: Both players propose a 4-digits number. Then, using a coin, they decide who ...
2
votes
0answers
454 views

A variation of Nim game

There are two players $X$ and $Y$. They write $N$ integers on paper $( A_1 , A_2 , A_3 , .... A_N )$. They have also $M$ integers $(B_1 , B_2 , B_3 , .... B_M )$ . Now, Player $X$ always takes ...
2
votes
0answers
96 views

Finding a Mathematical definition of a Discrete Time Game

Preface: Suppose we have a game world as depicted in the following figure: Where each of the white blocks is passable, And each of the black blocks is a wall and so impassable. Each of the Green ...
2
votes
0answers
256 views

The hardest game of mahjongg

I was playing Mahjongg solitaire the other day. It got me thinking... The board has $2n$ pieces at the beginning and assuming that the game is winnable. The game would be trivial if there would be ...