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

some amazing properties of combinatorial numbers

I want to prove $$ C_{2^{i+1}-k-1}^k=\frac{(2^{i+1}-k-1)(2^{i+1}-k-2)\cdots(2^{i+1}-k-(k-1))(2^{i+1}-2k)}{k(k-1)\cdots 2\cdot 1} $$ is even, for all $k=1,2,3,\cdots, 2^i-1$. Here $i\geq 1$. How to ...
1
vote
0answers
15 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
92 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
57 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
53 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
511 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
494 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 ...
2
votes
0answers
61 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
61 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 ...
6
votes
0answers
56 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 ...
2
votes
1answer
33 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
344 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
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 ...
4
votes
1answer
120 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
82 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
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
38 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
87 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
507 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
312 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
122 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
41 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
325 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
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
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 ...
2
votes
0answers
163 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
46 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, ...
0
votes
1answer
36 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
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.
0
votes
1answer
27 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
243 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
32 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
15 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
194 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
98 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 ...
7
votes
3answers
321 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, ...
113
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 ...
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 ...
12
votes
0answers
389 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 ...
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 ...
22
votes
2answers
631 views

The expected outcome of a random game of chess?

Imagine a game of chess where both players generate a list of legal moves and pick one uniformly at random. Q: What is the expected outcome for white? 1 point for black checkmated, 0.5 for a ...
1
vote
1answer
34 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 ...