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.

671 questions
29 views

The number of five digit natural numbers which contains exactly two distinct digits?

For example, How many 4 digit numbers are there which contains not more than 2 different digits? Answer is 576 The first (non-zero) digit of the number F (thousands digit) can be any one of nine. The ...
66 views

Winning strategy of a game on tuples of positive integers

Alice and Bob are playing a game in which they take turns modifying a $k$-tuple $(t_1,\ldots,t_k)$ of positive integers. Alice plays first. On each turn, a player subtracts a positive multiple of $t_i$...
20 views

The game of Brussels Sprouts

I read once about a variant of the game Sprouts called Brussels Sprouts. Instead of placing dots on a plane, one places $n$ $+$ signs instead. Each player, in turn, connects any two free legs, ...
31 views

Card Guessing Game Probabilities

Suppose we have a card game in which, for a standard deck of 52 cards, one card of each suit is selected at random and pulled out of the deck. The remaining 48 cards are shuffled together, and laid ...
63 views

Is there a reasonable one hour summary of Game Theory?

In his Topology and Geometry course on Youtube (http://www.youtube.com/watch?v=QzfZS3iopR0&t=10m7s), Tadashi Tokieda claims he can teach all of game theory in an hour. He seemed very sincere and ...
167 views

How many moves will it take to turn $100$ coins to the heads side up? [closed]

You have 100 coins on the table, all tails up. One move is turning any 93 coins over.How many moves will it take to get all the coins on heads? It's question that I found in mathematical "olimpics" ...
45 views

59 views

Who will be the winner if $A$ is always the first to go?

$A$ and $B$ play a folk game as follows. There are $n$ sticks on the table. Each person takes turns picking up the number of sticks that are one of three numbers $1,2$ or $3$. If the last person is ...
37 views

Expectation value of fighting time of Knight vs Monster problem

I get this problem when I play computer game. When I see my knight is attacking the monster, I think what is the expectation value of fighting time. My knight is much more powerful than the monster, ...
102 views

How to find the total number of auras possible for a tile of a given tier?

PLEASE NOTE! A different problem that uses the same ruleset (technically a subset of this one since i ask multiple questions here) that can be solved with brute force and pen-and-paper has been posted ...
113 views

The Connect Infinity game

Recently Joel David Hamkins posted an entry on the Connect Infinity game. Connect-$\omega$ is Connect Four but played on an $\omega\times n$ grid ($n$ finite)! The above shows $n=6$. The difference ...
66 views

Optimal strategy dice game: Dutch TrickTrack

I play a 2 dice game with 2 up to 7 players (could even be more) and I just can not figure out what the optimal strategy is. It is a really fast and easy game but the math is more difficult than you ...
35 views

Calculating Sprague–Grundy numbers for impartial game with a loop

Suppose we have a two-player game with states $\{A,B,C,D\}$ and allowable moves: $$A \to B, B \to A$$ $$A \to C, B \to C$$ $$C \to D$$ Since there are no moves starting from $D$, if a player is in ...
62 views

P-positions of Nim variant with multi-pile moves

I was looking at a variant of Nim that involves two piles of stones, let's say (m, n), where m and n represent the number of stones of the first and second pile, respectively. A valid move involves ...
66 views

How do I solve this combinatorics problem with conditions?

I have $N$ lattice points which are arranged linearly and equally spaced. I want to make connections(say with some wire or thread) with each lattice site with another. The first one has $N-1$ ...
32 views

Wythoffs Game -Game Theory

Suppose in the Wythoff’s game there are 40 matches in the first pile and 20 in the second pile and it is your turn to play. How would you play? Please assist in how to complete this problem.
37 views

Game on a number line

Define a game on a number line as follows: at the beginning, there are (possibly) some tokens at some negative integers on the number line. Each integer can hold any number of tokens. At each step, ...
59 views

Who has the winning strategy? [closed]

A $48 \times 29$ rectangle is divided into unit squares. Two players take turns to colour these squares black, as follows. At each turn, a player chooses a number of uncoloured squares that themselves ...
42 views

Game of Nim Sum Challenge Problem

Suppose in the game of Nim there are 72 chips in the first pile, 60 chips in the second pile, and 100 chips in the third pile and it is your turn to play. How would you play? Following the below ...
86 views

Alice and Bob Game 123456789

The number 123456789 is written on the blackboard. Alice and Bob play the following game, taking turns. At every turn, each player decreases by 1 or 2 any digit other than the leftmost digit, if the ...
57 views

Winning strategy in a number theory game

Two people play a game, lets call them A and B. There are $n$ stones on a table and players start to remove them. They can remove $p-1$ stones at once where $p$ is a prime number. Whoever takes the ...
52 views

Game where all positions specify the entire game history

I'm looking for an example of a game where, just by looking at the current game state, you can tell uniquely the entire game history. Are there any games with these properties? I'm looking for a ...
71 views

Game on a Graph

Assume a game on a Graph $G$ with two players called Alice and Bob. They alternate their moves and Alice always begins. In the beginning Alice puts a coin on arbitrarily vertex of the Graph. In ...
70 views

Find the average score obtained

Given a regular dice game in which each side has an equal probability of $1/6$, you roll the dice. If you get an even number, you roll two dice now and if the sum of the new values is again even, you ...
53 views

Optimal moves for maximizing perimeter? [closed]

Herman and Alex play a game on a $5 \times 5$ board. On his turn, a player can claim any open square as his territory. Once all the squares are claimed, the winner is the player whose territory has ...
173 views

Alice and Bob take turns to remove numbers from a list

Alice and Bob play the following game. In the beginning there is list of numbers $$\{0, 1, 2,\dotsc, 1024\}.$$ Alice starts, and removes 512 numbers of her choice. Bob continues and removes 256 ...
22 views

Commitment Games, Nash Equilibria and Subgame Perfect Nash Equilibria

Are all Nash equilibria found from the strategic form of a commitment game all subgame perfect Nash equilibria (SPNE)?
96 views

Tic-Tac-Toe on the Real Projective Plane is a trivial first-player win in three moves

Consider a $3 \times 3$ Tic-Tac-Toe board with opposite sides identified in opposite orientation. We play Tic-Tac-Toe in the Real Projective Plane. More precisely, consider a $3 \times 3$ Tic-Tac-Toe ...
65 views

Guess ball colors

7 people receive either a black or a white ball. They can only see the color of the others balls, but not their own. Both of the colors are equally likely. They play as a team a game of guessing their ...
24 views

Birthday line to get tickets in a unique setup [duplicate]

There is a long line of people waiting outside a theatre to buy tickets. The theatre owner comes out and announces that the first person to have a birthday same as someone standing anywhere before him ...
84 views

Amount of strategies in tic-tac-toe

So, I have this problem for my homework in which I'm asked to show that the amount of strategies for player number 1 in tic-tac-toe is between $$9*7^8*5^{48} \text{ and } 9*7^8*5^{48}*3^{192}$$ But I ...
61 views

Question about proportion of Nim positions

Let a Nim game be represented by a sequence of positive integers. We call a Nim of size $n$ when the sum of its elements is $n$. Let $a(n)$ be the number of Nim games of size $2n$ with Nim sum 0. ...
110 views

Could the Collatz Conjecture be related to Solitaire?

When observing different variations of the Collatz Conjecture, I found that stumbling across loops instead of watching the trajectory decay to one happens a lot. When playing a game of Klondike ...
29 views

Proving that the Nim-sum cannot be zero for two turns in a row

In proving certain results about Nim, I found a lemma that is causing me trouble: Lemma 1 If the Nim-sum is $0$ after a player’s turn, then the next move must change it. To prove this, let the ...
26 views

Is Nim a (strong) positional game?

A positional game is a kind of a combinatorial game described by: $X$ a finite set of elements. (Often $X$ is called the board and its elements are called positions.) $F$ a family of subsets of $X$. ...
I'd like to ask how to solve the quadratic nimber equation $x\otimes x \oplus b \otimes x \oplus c=0$, where $\otimes$ is nim multiplication and $\oplus$ is nim addition.