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

0
votes
0answers
28 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
41 views

explaining the pattern

I have been given the following math puzzle: you are given a matrix that is filled by the following rule: every cell i,j is evaluated by taking the lowest non-negative number that is not present in ...
0
votes
0answers
39 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.
6
votes
1answer
147 views
+100

Is it true that we can get zero for all $(x,y,z)\in\mathbb{N}^3$?

There are three distinct positive integers $x$, $y$, and $z$. We can choose two numbers $a,b\in\{x,y,z\}$, where $b\leq a$, then replace $b$ by $2b$ and replace $a$ by $a-b$. Is it true that there ...
0
votes
1answer
23 views
+50

Reducing an I-optimal problem to a Pareto-optimal problem

Given a set $\textbf y\subset\mathbb R^2$, let $y = (y_1,y_2), y'=(y'_1,y'_2)\in\textbf y$ be elements of that set, let $\alpha_{min}\in\mathbb R$, $\alpha_{min}<1$, $\alpha_{max}\in\mathbb R$, ...
-1
votes
0answers
19 views

most competitive game formula

I am creating a game and have variables that I need to figure out. So the game will consists of a number of available options. I'm trying to find how many picks per player and number of players will ...
0
votes
1answer
24 views

Biobjective optimisation, pareto non-domination

Ok, so, I have a function $f_I(y_1, y_2) = \max\{\alpha y_1 + (1-\alpha)y_2:\alpha\in[\alpha_{min},\alpha_{max}]\}$ that I'm trying to minimise, and I'm asked to find, amongst a set of vectors $y$, ...
1
vote
0answers
26 views

Coloring the balls

Bob and Alice are playing a game. Initially they have balls of black and white color arranged together in a line. Rules of the game are as follows: 1.They start the game by going from right to left ...
0
votes
0answers
11 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 ...
3
votes
2answers
174 views

Why does the theory of the game Nim use binary digital sums?

So I was reading "Graphs and their uses" by Oystein Ore and I came across a section about the game called Nim. Now the author takes as granted the binary digital sums as a way of solving the game. The ...
10
votes
1answer
217 views

Bidding Tic Tac Toe

In regular tic tac toe, both the players get alternate chances. This is a variant of that. Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$. Both ...
1
vote
1answer
86 views

Why does strategy-stealing not work for Go?

The related Wikipedia article states: In Go passing is allowed. When the starting position is symmetrical (empty board, neither player has any points), this means that the first player could steal ...
14
votes
2answers
227 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
2
votes
1answer
30 views

Modified parcheesi game

A "modified Parcheesi" game starts with the following position: First $x$ flips a fair coin. If heads he can move two spaces or pass. If tails he can move one space or pass. If he occupies the ...
0
votes
0answers
7 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 ?
3
votes
1answer
80 views

Can the wolves catch the hare?

Say you have 7 positions. 1 Hare and two Wolves in the following starting positions:    H o     o W   W  o   o The hare can take a step of size 2. The ...
0
votes
2answers
39 views

Recreational chess questions based on the knights

I basically know whether the following statements are true, but I would like to know how they are proved. A knight kept anywhere on an empty chess board can not reach its adjacent square in exactly ...
1
vote
1answer
33 views

A 2 Player Pure Strategy Game

There are two players each has $n$ balls. At the same time they distribute their balls among $m$ boxes. For each box 1 point is given to the player with more balls and zero points to other one (When a ...
0
votes
2answers
38 views

Is this proposition posible? [duplicate]

In a board, you have $13$ White round pieces, $15$ Black round pieces, and $17$ Red round pieces. In each round you can choose two different color pieces and change them with two other pieces of ...
1
vote
0answers
44 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 ...
4
votes
0answers
41 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) ...
0
votes
2answers
26 views

prove that if $n=k$ then white has a winning strategy in $S_{n,k}$.

Black and white play sequentially the game $S_{n,k}$ with $k,n\in \mathbb N \space 0\leq k\leq n$ the game board consists of all subsets $A\subseteq\{1,2,...,n\}$ such that $1\leq |A|\leq k$. every ...
1
vote
2answers
81 views

Counting problem about pirates and gold coins [duplicate]

Five pirates find a cache of 500 gold coins. They decide that the shortest pirate will serve as the bursar and determine a distribution of the coins however he sees fit, and then they all will vote. ...
2
votes
1answer
29 views

Game removing tokens on number line

A two-player game begins with $k<2^n$ tokens placed at point $0$ on the number line spanning $[0,n]$. Each round, player $A$ chooses two disjoint, non-empty sets of tokens $X,Y$. Player $B$ takes ...
1
vote
2answers
33 views

Combinatorics For $4$ Pool Balls

There lie $4$ pool balls on a pool table: two striped and two plain. Two of the pool balls are selected at the same time, at random. Given that one of the selected balls is striped, what's the ...
3
votes
1answer
26 views

Game picking cards so that sum is divisible by $25$

Adele and Bryce play a game. There are $50$ cards, numbered $1,2,\ldots,50$. They take turns alternately picking a card, with Adele going first. If at the end, the sum of the numbers on Adele's cards ...
3
votes
3answers
75 views

Card Game Probability 13 Card Hand

Me and my friends play a four person poker style card game. Each person is dealt 13 cards, and it is a standard trump card game. Now, as the standard, a five card flush beats a five card straight, but ...
7
votes
2answers
283 views

Converting a Gomoku winning strategy from a small board to a winning strategy on a larger board

Gomoku is the game where Black and White take turns placing stones of their own color, and the winner is the player who first gets five of their own stones in a row. Black moves first. In Gomoku on ...
0
votes
1answer
26 views

Proof sprague-grundy value is 0 if and only if it is losing position

So, i take this game theory module this summer, and i encountered this exercise problem, i tried to do this by induction by have terminal position (grundy-value = 0) as base case, but can't figure out ...
0
votes
0answers
28 views

Game placing numbers in increasing order

Let $k\leq m\leq 100$ be positive integers. Aaron and Britney play a game on a $1\times m$ board, using $100$ paper pieces numbered from $1$ to $100$. The game has $k$ turns. In each turn, Aaron ...
1
vote
1answer
43 views

Game of polygons

Initially, there is a polygon with N vertices drawn in the plane. The polygon is strictly convex, i.e., each internal angle is strictly smaller than 180 degrees. The vertices of the polygon are ...
2
votes
2answers
89 views

Gomoku on an infinite big board

I always used to play Gomoku in school on paper, and if we reached the edge of the field, we just put another one at that side. And now I just saw that black can always win on 1 15x15 board. But what ...
8
votes
1answer
84 views

Game replacing two numbers by mean

Alicia and Bart plays a game. Alicia first writes $100$ real numbers on the board. After that they move alternately; Bart goes first. In every move, the player chooses two numbers, erases them, and ...
1
vote
1answer
168 views

What to do with a random variable when we know its mean and variance but does not know which distribution it is?

Let Y be a random variable with mean μ and variance σ^2 where the support is (0, ∞). Suppose you are offered to play a game where you choose a number z between (0, ∞). If a realization of the random ...
2
votes
1answer
81 views

Commutative Algebra and Game Theory

Is there any relationship between commutative algebra and game theory? For example, have any tools in commutative algebra been applied to game theory? A text or reference would be ideal, but I'd be ...
3
votes
1answer
65 views

Characteristic 3 analogue of nimbers?

Finite nimbers are a way of turning the natural numbers (finite ordinals) into a characteristic 2 field. Addition in this field is found by writing the numbers in binary and adding without carry, ...
6
votes
2answers
112 views

Eating chocolate game on grid

Given is a chocolate of size $m\times n$. Anne and Birgitte plays a game, with Anne starting. In each turn, the player has to divide the chocolate into two rectangular parts along the lines, and eat ...
1
vote
5answers
121 views

Game Theory - First move vs second move advantage?

This question came up in a lunchtime discussion with coworkers. None of us are professional mathematicians or teachers of math, and we weren't sure how to get the answer. I apologize in advance if my ...
0
votes
1answer
87 views

Nim Sum Game Variant

Suppose there are black and white balls in a box. The initial number of white balls is m and the initial number of black balls is n. This is a two player game. Each player can do the following taking ...
1
vote
1answer
94 views

Counting all possible board positions in Quoridor

I'm trying to figure out how many possible board positions there are for the game Quoridor. I think sorting out the legal positions from the illegal positions will be difficult, so to start I'm trying ...
0
votes
1answer
69 views

Pigeon-hole principle applied to the game of tic tac toe

In a game of tic tac toe, noughts and crosses are drawn inside an unoccupied cell of a 3 x 3 matrix by two players I, II in alternating moves. Player I draws crosses and Player II draws noughts. The ...
0
votes
1answer
29 views

How to write induction proof of Sprague-Grundy function for subtration game?

So lets say that S={1,2,3} I find the sequence of Sprague-Grundy function. How do I justify my answer using induction?
2
votes
0answers
74 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 ...
0
votes
0answers
28 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 ...
0
votes
1answer
83 views

Relationship between regular Nim and Lasker's Nim

So I'm trying to do qn $6$ (on pg I-13) about staircase Nim in Game Theory by Ferguson Game Theory, Ferguson and it's asking to prove that $(x_1, x_2, \ldots, x_k) \in P $ only if $(x_1, x_3, x_5, ...
1
vote
1answer
35 views

CGT: value of sum game is sum of values of games

I am involved in a little study about combinatorial game theory. The study makes heavy use of the fact that, at least in a simple combinatorial game called domineering, the value of the sum game is ...
1
vote
2answers
109 views

Probability that 20 sided die beats 12 sided die with reroll

Alice rolls a 12 sided die (the faces labeled 1 through 12) and Bob rolls a 20 sided die (the faces labeled 1 through 20). After seeing their roll (but not the other person's roll), each person can ...
0
votes
0answers
43 views

countable subset of surreal games

Surreal numbers are the largest possible structure to have a complete order. Games are an extension of the Surreals which only admits a partial order. Along with being larger, smaller or equal to each ...
14
votes
1answer
492 views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...
1
vote
0answers
66 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 ...