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

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

In the card game “Projective Set”: Compute the probability that $n$ cards contain a set

In the game of Projective Set, it turns out that any seven cards contain a projective set. For fewer than 7 cards, how can we determine the probability that one or more sets exist (in terms of the ...
4
votes
1answer
100 views

In the card came “Projective Set”, show that 7 cards do always contain a set. [duplicate]

In the game of Projective Set, it turns out that any seven cards contain a projective set. How can one prove this? And for fewer than 7 cards, how can we determine the probability that one or more ...
4
votes
0answers
56 views

Wizard against two dwarfs: guess the whole function

An evil wizard plays the following game with two dwarfs $A$ and $B$: he thinks of a function $f:\mathbb{R}\to\mathbb{R}$ (which is not required to have any regularity properties, such as ...
2
votes
0answers
66 views

Alice and Bob grid game

Given a $N$ x $N$ matrix with some black and white cells. Now Alice and Bob start playing a game alternatively. Alice moves first. Game proceed as follow : When a player makes a move, he/she needs ...
1
vote
2answers
63 views

Sierpinski triangle game for 3 players

The players are red, green and blue. The game is played on a n-deep Sierpinski triangle. Each player colors a (black) triangle, starting at one of the main vertices. They then take turns to color an ...
2
votes
1answer
36 views

Perudo Game - probability of succes for my call

I'm making a computer program that should play as a bot against other student's bots as ICT project at school. The game is Perudo. In this part of the program I want to know what's the probability of ...
9
votes
4answers
351 views

Big List of examples of recreational finite unbounded games

What are some examples of mathematical games that can take an unbounded amount of time (a.k.a. there are starting positions such that for any number $n$, there is a line of play taking $>n$ times) ...
6
votes
0answers
69 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 ...
3
votes
0answers
46 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 ...
3
votes
1answer
43 views

Why can a Nim sum be written as powers of 2?

I have this confusion. Why do we express a nim sum as powers of 2 and why do nim sums cancel in pairs of 2 only? For instance, let's take the nim game(6,10,15) Now clearly *6 = * $2^2$ + * $2^1$ *10 ...
3
votes
1answer
88 views

Donald Knuth's Nontransitive Bingo Cards

In Time Travel and Other Mathematical Bewilderments, Martin Gardner presents a set of four nontransitive bingo cards designed by Donald Knuth (pp. 61). The rules are that the first player to complete ...
4
votes
0answers
42 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 ...
2
votes
1answer
130 views

Lemke-Howson pivoting in degenerate bimatrix games

I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For ...
1
vote
1answer
39 views

Strategy in a blocking game

In this blocking game for 2 is there a clear strategy for the first player, the second player or neither? You have a 5 x 5 grid of squares. The players take turns laying dominoes so as to cover a ...
0
votes
1answer
21 views

N choose K and assumptions.

I have a process by which people must compare a bunch of items against each other in pairs. For now, let's say we're comparing two at a time from a set of six items. The problem is that people end up ...
0
votes
1answer
40 views

What is the probability for …?

You start at the black field bottom left and have to move op til top right black field by only move right and up. What is the probability for moving over the white field with the cross in your way to ...
2
votes
0answers
166 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$ ...
-1
votes
1answer
326 views

stable marriage problem doubt

Suppose we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might ...
0
votes
0answers
151 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
1answer
47 views

Does Alice has a winning strategy?

There are $n$ stones, Alice and Ben are playing a game that, each one take some stones in turn, and each turn one can only take 1, 2, 4, or 6 stones, the one take the last stone wins. If Alice is the ...
1
vote
0answers
51 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, ...
2
votes
2answers
89 views

Explaining a Pattern in a Matrix Generated by Minimum Excluded Number in Rows & Columns

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 ...
0
votes
0answers
44 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.
17
votes
2answers
491 views

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
37 views

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$, ...
0
votes
1answer
29 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
33 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
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 ...
4
votes
2answers
196 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
249 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
99 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
242 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
34 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
10 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
94 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
48 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
35 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
64 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
45 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
29 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
117 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
38 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
38 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
27 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
97 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 ...
8
votes
2answers
611 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
39 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 ...
1
vote
1answer
46 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 ...