Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorial-game-theory]

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.

17
votes
4answers
2k views

Reference for combinatorial game theory.

What is a good reference material for elementary combinatorial game theory? By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
4
votes
1answer
495 views

Tutorials for Sprague-Grundy Theorem/Nimbers?

Help needed in understanding S-Grundy Number , any good tutorial. I am trying to solve Mathalon Problem 146 S-Grundy Game (dead link).
3
votes
2answers
17k views

Game combinations of tic-tac-toe [closed]

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)? So for example a game which looked like: (...
9
votes
2answers
4k 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 ...
3
votes
2answers
1k views

Game involving tiling a 1 by n board with 1 x 2 tiles?

Consider a $1$ by $n$ tiled rectangle. You want to play a game with one opponent in which you place $1$ by $2$ "dominoes" on this rectangle. The player who places the last domino wins. Which player ...
55
votes
3answers
3k views

Alice and Bob play the determinant game

Alice and Bob play the following game with an $n \times n$ matrix, where $n$ is odd. Alice fills in one of the entries of the matrix with a real number, then Bob, then Alice and so forth until the ...
10
votes
3answers
1k views

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
3
votes
1answer
149 views

Name for a certain “product game”

Let $G,H$ be two (combinatorial impartial) games. Consider the following new game $P$: The positions are the pairs of positions of $G$ and $H$. A move in $P$ is a move in $G$, or a move in $H$, or a ...
0
votes
1answer
80 views

How to determine the size of the complete game tree for basic [M]?

You can read the rules of the game here, or actually play it free on the mobile mbrane app, but it's not required to address the question. Essentially: players take turns placing integers onto an ...
340
votes
0answers
13k 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 ...
24
votes
3answers
781 views

Hat 'trick': Can one of them guess right?

There are $n$ boys and $n$ girls. Each of them is given a hat of only 4 possible (known) colors and doesn't know its color. Now each can only see all the colors of hats of those of the other gender ...
37
votes
9answers
76k views

Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
12
votes
5answers
1k 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. ...
4
votes
1answer
810 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 ...
3
votes
1answer
1k views

Nimbers for misère games

Let $G$ be an impartial combinatorial game. I claim that there is a game $G'$ such that $G$ (without terminal positions; see below) under the misère play rule is equivalent to $G'$ under the normal ...
5
votes
1answer
240 views

Game: two pots with coins

Rules of the game with two players. First player puts any number of coins in the first pot. Then second player, knowing that number, puts any amount of coins in the second pot. Then they in turns (...
4
votes
2answers
14k views

Winning strategy for a matchstick game

There are $N$ matchsticks at the table. Two players play the game. Rules: (i) A player in his or her turn can pick $a$ or $b$ match sticks. (ii) The player who picks the last matchstick loses the game....
3
votes
4answers
283 views

What does she mean by star?

I was looking at this video http://www.youtube.com/watch?v=ygqIfLHGTu4&feature=g-all-f#t=06m33s33 and i wondered what she means by star. How is this number defined and where does it come up. ...
1
vote
0answers
53 views

Two players choosing one of three numbers

$A$ and $B$ play the following game. Initially, for positive integer $n$, each player takes turns choosing one of three numbers: $1$ the number of digits of $n$ the sum of the digits of $...
6
votes
1answer
135 views

Filling an array(Putnam)

Alan and Barbara play a game in which they take turns filling entries of an initially empty $ 2008\times 2008$ array. Alan plays first. At each turn, a player chooses a real number and places it in a ...
4
votes
2answers
109 views

Are there combinatorial games of finite order different from $1$ or $2$?

Are there any combinatorial games whose order (in the usual addition of combinatorial games) is finite but neither $1$ nor $2$? Finding examples of games of order $2$ is easy (for example any ...
1
vote
3answers
802 views

Is there any winning strategy? 2015 and Game with marbles!!!

Two players, Alex and Brad, take turns removing marbles from a jar which initially contains $2015$ marbles. Assume that on each turn the number of marbles withdrawn is a power of two. If Alex has the ...
1
vote
2answers
101 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. The ...
0
votes
2answers
156 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 ...
49
votes
3answers
6k views

Sharing a pepperoni pizza with your worst enemy

You are about to eat a pepperoni pizza, which is sliced into eight pieces. Each pepperoni will unambiguously belong to some slice (no pepperoni is "between" slices). The caveat is that you have to ...
15
votes
5answers
866 views

A Knight and Knave Problem

There are $69$ people in a room, of which $42$ are truth-tellers (they always tell the truth) and the rest are liars (they can lie or tell the truth). You are allowed to ask any person $A$ whether any ...
20
votes
2answers
509 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
8
votes
1answer
272 views

Identify a truth-teller among a group of truth-tellers and (honest) liars.

This question is inspired by this thread. In that thread, a liar may both tells lies and truths. However, in my version, liars always lie. Main Question. A group of people consists of $m$ truth-...
9
votes
1answer
166 views

What is the winning strategy for this Game on the Power Set

Given a finite set, players alternately choose proper subsets. Once a subset has been chosen, none of its subsets may be chosen later. The last player to move wins. I figured out that, with optimal ...
12
votes
1answer
2k views

Determinant game - winning strategy [duplicate]

I came across this problem while looking at Putnam problems a while ago: Alan and Barbara play a game in which they take turns filling entries of an initially empty $2008 \times 2008$ array. Alan ...
7
votes
0answers
281 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) ...
12
votes
2answers
1k views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
11
votes
5answers
1k 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) ...
11
votes
2answers
754 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. ...
7
votes
1answer
393 views

Alice and Bob make all numbers to zero game

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn. In a turn : A player selects one of the integers, divides it ...
7
votes
1answer
2k views

Stone picking puzzle

Two players are playing a stone picking game. The players pick a stone from two pile of stone in turn. One can choose to pick any number of stones from either pile, or pick the same number of stone ...
6
votes
1answer
917 views

Optimal strategy for this Nim generalisation?

Consider the following game: There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to $N$ piles (at least 1). It is allowed to remove a ...
6
votes
1answer
110 views

Winning strategy in $(2n+1) \times (2n+1)$ matrix game.

Edit: A few minutes after posting this question (that I had been thinking about for about a day) I figured out the answer in the $3 \times 3$ case; see my answer below. However, the question might ...
4
votes
1answer
525 views

A question about something in Conway's “On Numbers and Games”

In the book mentioned in the title, which deals with (among other things), Conway's "surreal numbers", there is a small section (pp. 37-38) where the "gaps" in the surreal number line are discussed. ...
4
votes
1answer
788 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 ...
4
votes
1answer
236 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 ...
12
votes
2answers
1k views

board game: 10 by 10 light bulbs, minimum switches to get all off?

Hy all! My problem is as follows: There's a board of 10 by 10 light bulbs. (So it's a square with 10 columns and 10 rows.) Every single bulb has got its own switch. However, something went wrong and ...
10
votes
3answers
6k 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 ...
7
votes
1answer
648 views

Traversing the infinite square grid

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board. At move $n$ one must take $a_n$ steps in one of the directions, north,south, ...
6
votes
1answer
2k views

How many different chess-board situations can occur?

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist? Upper bound: Well, you have 16+16 = 32 chess pieces ...
5
votes
2answers
42k views

Counting to 21 game - strategy?

In a game players take it in turns to say up to 3 numbers (starting at 1 and working their way up) and who every say's 21 is eliminated. So we may have a situation like the following for 3 players: ...
4
votes
3answers
1k views

Trying to find the name of this Nim variant

Consider this basic example of subtraction-based Nim before I get to my full question: Let $V$ represent all valid states of a Nim pile (the number of stones remaining): $V = 0,1,2,3,4,5,6,7,8,9,10$ ...
8
votes
1answer
424 views

In what way is combinatorial game theory connected to the rest of mathematics?

Since my University library lists Conway's "Winning ways for your mathematical plays in the section "recreational mathematics" alongside books on origami and puzzles, I wondered to what extent game ...
4
votes
2answers
7k views

TicTacToe State Space Choose Calculation

I understand there are numerous questions around the internet about the state space of tic-tac-toe but I have a feeling they've usually got it wrong. Alternatively, perhaps it is I who have it wrong. ...
4
votes
1answer
132 views

Ring structure on subsets of the natural numbers

Let $$\mathcal{N}=\{\{k_1,\ldots,k_s\}:\ s>0,\ \mbox{and the}\ k_i\ \mbox{are non-negative and pairwise different integers}\}\cup\{\emptyset\}.$$ Note that there is a bijection with the naturals, $$...