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
1answer
21 views

Can someone please help me understand what a “player set” is in extensive form game

my text defines player set as: In N-player game $g$, each non-terminating node is partitioned into $N+1$ sets $g^0, ... g^N$. These are player sets. However it makes no attempt to identify ...
7
votes
3answers
2k views

How many turns can a chess game take at maximum?

The shortest number of moves that a game of chess can have is 2, as far as I know: White moves pawn from f2 to f3, black moves ...
0
votes
0answers
14 views

Is this general variant of nim NP-hard to decide who has a winning strategy?

Suppose there are $n$ piles of stones, where pile $i$ originally has $m_i$ stones, and each pile has a maximum number of stones $k_i$ that can be taken on each turn. Fix integer $N \geq 1$. Suppose ...
0
votes
1answer
34 views

Why does the 1st player in this subset take-away game always have a winning strategy?

This is a HW problem of mine that I cannot, for the life of me, figure out. There is a take-away game where there are a number of elements A, and the person that wins is that last person to remove a ...
3
votes
2answers
60 views

Proving the rules of a complicated game are well defined

What strategy could one use to formally model a game and prove that the rules do not lead to any self contradiction? A major example that comes to mind is Magic the Gathering. The card ...
10
votes
2answers
548 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
10
votes
2answers
590 views

Breaking chocolate bars game

About two weeks ago, a friend of mine taught me the following game without his knowing the answer. It may be famous, but I haven't known it. There are $N\ (\in\mathbb N)$ chocolate bars composed of ...
12
votes
3answers
146 views

Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected). Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such ...
4
votes
1answer
51 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 ...
1
vote
1answer
47 views

What is the mixed strategy equilibrium bid, if any, for complete information auction games with minimum bid?

Consider the following complete-information, auction game. There are two players $i=1,2$. Each bids simultaneously a value $b_i\in[0,\infty)$. The payoff function is symmetric: $$ \pi_i ...
-1
votes
1answer
31 views

Sprague–Grundy numbers

I would appreciate if someone can help me understand the columns of the table in this blog: http://lbv-pc.blogspot.co.uk/2012/07/treblecross.html . The author writes he leaves this as an exercise to ...
0
votes
0answers
18 views

super-additive, sub-additive, and shapely value limitations?

I am working on the coalition formation. Most of the scientist used concept of shapely value for distributing the utility among the members of coalition. Up to my understanding, shapely value is good ...
2
votes
1answer
60 views

NP combination puzzle (Klotski)

I've written a C++ program to solve sliding puzzles games such as UnblockMe and Car Parking. I'm quite happy about it, since it solves various schemes in less than a second. Recently I fed the game ...
8
votes
1answer
152 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 ...
6
votes
0answers
72 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 ...
4
votes
1answer
567 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 ...
4
votes
2answers
118 views

Maths Puzzle: Partitioning a set into two disjoint sets

Le $X$ be the set of all non-empty subsets of $\{a,b,c,d,e,f\}$. So $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; i.e., $|X|=63$. We want to partition $X$ into ...
1
vote
0answers
24 views

Multi-dimensional naughts and crosses: victory for first player?

In a $2$-dimensional checkerboard which is $2\times2$, the player going first necessarily achieves $2$ in a row. In a $3$-dimensional board which is $3\times3\times3$, a player going first using a ...
1
vote
1answer
69 views

Pseudo-Surreal numbers are analogous to?

I've been exploring surreal numbers. Real equivalent of the surreal number {0.5|} I see that pseudo-surreal numbers seem to have an interesting branch of game theory. Still having a form of {x|y}, ...
0
votes
1answer
182 views

King and Devil problem

On a unlimited two-dimensional plane, the plane is separated into two-dimensional grid point by line $x=k$, $x=-k$, $y=k$, $y=-k$ ($k$ is integer). There is a game like this : A king could move to any ...
3
votes
1answer
50 views

An inequality relating to moves to P-positions in Nim

I have been researching this variant of Nim. I have been unable to prove the following claim. What is annoying is that I feel I am missing something really obvious. Does anyone have any ideas on how ...
4
votes
1answer
62 views

“On Numbers and Games” or “Winning Ways for Your Mathematical Plays”?

I'm really interested in John Conway's work on games and I want to spend my winter reading something of his but I'm not sure between "On Numbers and Games" or "Winning Ways for Your Mathematical ...
3
votes
1answer
162 views

Optimal strategy for 2 players Lights Out game variation

Consider a turn-based game for 2 players. They're both playing on the same board. The board is 8x8, randomly generated and each cell has 0 or 1 (with equal probabilities), for example: ...
1
vote
0answers
33 views

How is Wythoff's Theorem proved?

Specifically, how does one prove the following? Suppose $(a,b)$ is not of the form $(A_n,B_n)$, where $A_n=\lfloor n \phi \rfloor$ and $B_n= \lfloor n \phi^2 \rfloor$. Then there is a move in ...
0
votes
0answers
38 views

Solving a Recurrence for a Mathematical Game

The problem is: Two players take turns removing coins from a pile. There are initially $n$ coins, and on each turn, a player can remove $a_1, a_2, \dotsc, a_k$ coins. The player who cannot remove ...
0
votes
0answers
78 views

How many ways we can arrange numbers such that sum of arrangement will be a given number

we have a value $p$ and we have to arrange numbers at $p$ places such that no number is greater that $p$ and no number is less than $0$ and also sum of arrangement should be a given number (suppose ...
0
votes
0answers
45 views

A Good book for Combinatorial Theory [duplicate]

I am looking for a good book on Elementary Combinatorics (Olympiad level). For some reason I do not like Lint. I am currently reading "A Walk Through Combinatorics" by Miklos Bona and I find it really ...
8
votes
4answers
429 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
201 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
124 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
54 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
76 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
66 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}$ ...
135
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
60 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
233 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 ...
3
votes
0answers
31 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
120 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
95 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 ...
3
votes
2answers
536 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 ...
1
vote
2answers
76 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
69 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
521 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
99 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
124 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
59 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
98 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 ...
4
votes
0answers
56 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
78 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
125 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 ...