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

3
votes
1answer
41 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 ...
10
votes
1answer
102 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
45 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
93 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
28 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
31 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 ...
4
votes
1answer
544 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 ...
0
votes
0answers
58 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
44 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
415 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
196 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
103 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
46 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
75 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
54 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}$ ...
128
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
50 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
223 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 ...
2
votes
0answers
26 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
115 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
90 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
68 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
527 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
72 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
51 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
435 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
97 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
58 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
92 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
67 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
110 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
520 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
323 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
228 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
48 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
40 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
24 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
338 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
498 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
159 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
180 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
54 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
38 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
46 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
282 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 ...