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

4
votes
1answer
23 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
6 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
71 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
35 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
31 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
36 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
37 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
25 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
64 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
28 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
32 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
66 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
168 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
22 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
26 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
42 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
80 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
82 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
165 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
75 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
55 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
100 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
98 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
71 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
78 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
59 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
23 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?
0
votes
0answers
122 views

N piles games with consecutive piles move

There are 6 piles of stones in a round configuration. In a single move, a player selects 3 consecutive piles, and removes some stones from 1 or more of these piles. (at least 1 stone must be removed ...
2
votes
0answers
68 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
27 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
48 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
33 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
91 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
34 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
485 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
63 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 ...
0
votes
0answers
28 views

Mex and Grundy Numbers explanation

I've been reading this small tutorial on Nimbers and game theory. Could someone explain why the mex rule governs the nimber of a game position? See: http://en.wikipedia.org/wiki/Mex_(mathematics) ...
4
votes
1answer
60 views

Optimal strategy for this Nim generalisation?

Consider the following game: There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to $N$ piles (at least 1). It is allowed to remove a ...
18
votes
2answers
376 views

Game involving points on $[0,1]$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you ...
7
votes
2answers
123 views

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
1
vote
1answer
41 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
1
vote
1answer
62 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
1
vote
4answers
105 views

Probability of drawing at least 1 red, 1 blue, 1 green, 1 white, 1 black, and 1 grey when drawing 8 balls from a pool of 30?

Given a pool of 30 balls (5 of each color). When drawing 8 balls without replacement, what is the probability of getting at least one of each color? Related: Probability of drawing at least one red ...
1
vote
1answer
69 views

Subtraction Game

I recently read about the Nim Subtraction Game. I have a variant, Suppose you have N stones and two players Alice and Bob, who can choose to pick either 1 stones or K stones. If Alice plays first when ...
0
votes
1answer
25 views

Bernouilli trial with variable number of experiments

I'm kinda stuck on a probability problem I encountered in designing a game. Here is its description : I'm calculating the number of turns (Tf) before a integer variable (A) reaches 0. Each turn, A ...
6
votes
6answers
411 views

Brain teaser Strategic choice… [closed]

$X$ and $Y$ are playing a game. There are $11$ coins on the table and each player must pick up at least $1$ coin, but not more than $5$. The person picking up the last coin loses. $X$ starts. How many ...
2
votes
1answer
45 views

2 player game subtracting perfect squares from a given number

this is my first question on these forums. I apologize in advance if I've overlooked a rule or done something wrong. Unfortunately, I can't remember where I came across this problem, but it's been ...
1
vote
1answer
81 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...