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

7
votes
4answers
396 views

Does a finite game that cannot be drawn imply a winning strategy exists?

The author of this page, about a simple game (Chomp) http://plus.maths.org/content/mathematical-mysteries-chomp makes the following statement: "One of the players is sure to have a winning strategy. ...
1
vote
0answers
189 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, ...
8
votes
0answers
86 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 ...
0
votes
1answer
39 views

Game with matches. Very interesting mathematical problem.

Suppose you have a set of matches. You arrange them in 9 rows such that the first row has one match the second two matches the third three and so on until the ninth row which has nine matches. There ...
2
votes
1answer
70 views

A game with rice

You have $N$ rices, and K places. You can put or take a rice in place numbered $1$ at any time. You can put a rice or take a rice from a place numbered $i$ iff there is a rice at a place $i-1$. For ...
2
votes
1answer
47 views

Number of paths that lie under the diagonal

Consider a grid in $\mathbb{N}_0^2$. We can draw a path in it by traveling from point to point via a horizontal line segment to the right or vertical line segment going up. Let $k,n \in \mathbb{N}$ ...
123
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 ...
0
votes
1answer
38 views

Game theory question- boxes

There are two players 1 and 2, and the game begins with player 1 selecting one of the boxes marked 1 to 16. Following such a selection, the selected box, as well as all boxes in the square of which ...
1
vote
0answers
214 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
20 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 ...
4
votes
1answer
104 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 ...
0
votes
2answers
82 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
0answers
61 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 ...
3
votes
2answers
523 views

Chess Board and Knights

I can't solve this question. Anyone knows how I must solve? You have a 6x3 chess board. How many forms exist to put a Knight in a square and with valid moviments pass in all squares but only one time ...
4
votes
1answer
516 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
1
vote
2answers
67 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
39 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
369 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) ...
2
votes
2answers
91 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 ...
4
votes
1answer
122 views

Who has a winning strategy in “knight” and why?

Perhaps, this game is already known, but I did not find anything about it, I call it "knight". The rules : Player 1 chooses the starting square of a knight on a normal 8x8 - chessboard. The ...
0
votes
1answer
57 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 ...
1
vote
2answers
88 views

Optimal strategy in a match picking game

I faced this exercise making a practice exam and couldn't find the answer: Question: 2 players play the following game with matches. Each player can take in turn some matches from a bunch of ...
3
votes
0answers
49 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
54 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
101 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 ...
7
votes
1answer
515 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
5
votes
3answers
316 views

pseudo numbers and surreal numbers

A surreal number $\{x_L\|x_R\} \in No$ is a number when for all $\xi\in x_L$ and all $\eta \in x_R$ we have $\eta > \xi$. All the things $\{x_L\|x_R\}$ which are not of that form are called ...
2
votes
1answer
165 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 ...
4
votes
0answers
44 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 ...
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 ...
-1
votes
1answer
330 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
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 ...
17
votes
2answers
492 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
0answers
153 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 ...
2
votes
0answers
173 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$ ...
0
votes
1answer
50 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 ...
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
0answers
45 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
1answer
31 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$, ...
10
votes
1answer
258 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
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
205 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 ...
1
vote
1answer
103 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
243 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 ...
7
votes
3answers
331 views

Why are the surreals considered “recreational” mathematics?

One of my college math professors once remarked to me that it was interesting that John Conway's two "biggest" contributions to math were both recreational: the Game of Life and the Surreals. No one, ...
2
votes
1answer
36 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
97 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 ...