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.

0
votes
0answers
47 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 ...
0
votes
2answers
148 views

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

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" ...
2
votes
0answers
42 views

Games and Dyadic Rationals

Suppose $a$, $b$, and $c$ are dyadic rationals, where their corresponding numbers (games) are $A$, $B$, and $C$ respectively. Prove that $a+b=c$ if and only if $A+B\sim C$ (or $A+B$ is equivalent to $...
0
votes
2answers
25 views

A variation on NIM game

Problem: We have two heaps of coins with 100 and 99 coins. Two players take some coins alternately, either at least one, at most 10, from the first one, or at least one, at most 9 from the second. The ...
0
votes
1answer
32 views

Minimize or Maximize The NimSum at a certain step?

Suppose, we are playing a nim game. And We can make say N possible moves, each generating some NimSum Value. For a Winning, Strategy, Should we chose the move with minimum nimsum?
0
votes
1answer
24 views

Core of the game and shapley value

Five political parties, A, B, C, D, E take part in the following cooperative game. The number of votes controlled by individual parties are a = 9, b = 9, c = 10, d = 60, e = 60, Any coalition that ...
0
votes
0answers
27 views

Game: Removing Matches from Stacks

Given two players $A$ and $B$ and two piles of matches with size $N$ and $M$ respectively. Player $A$ goes first and players alternate turns. On each turn, the player must remove a positive number of ...
1
vote
1answer
39 views

how do you calculate the grundy number?

I want to calculate the grundy number of these 4 normal-play nim heaps: 0, 7, 7, 7 I'm confused when comparing two wikipedia pages: sprague-grundy suggests I should ...
0
votes
1answer
25 views

I need help understanding the shapely value formula for voting games

A company has 4 shareholders with 10 20 30 40 stock respectively, a decision can be made by the shareholders with the majority of the shares ie over 50 percent, determine the voting power of each ...
0
votes
1answer
64 views

A game relevant to moving a stone.

There is a straight line of $10000$ cells connected together . It contains $n$ stones at coordinates $p_i(1\le p_i\le 10000,i=\overline{1,n})$. A and B plays a game as follow: 2 players take turns ...
0
votes
1answer
61 views

A game relevant to piles of coins.

There are $N$ piles of coins, the number of coins of a pile is $p_i(1\le i\le N)$. ($N$ is a prime number and $2\le N\le 30$). A always plays first. A and B move in alternating turns. During each ...
0
votes
0answers
16 views

Winning strategy using prime divisors. NIM varient.

In this game, two people take turns removing sticks from a pile that begins with x sticks. The person who takes the last stick wins. A person removes either one stick or p sticks, where p is a prime, ...
1
vote
1answer
48 views

Combining Nim Games

I was reading the Wikipedia article on the Sprague-Grundy theorem, and I can't get through their example for combining games. The example combines two sets of three heaps. The first set has 1, 2 and ...
3
votes
1answer
55 views

A game based on cutting rectangles from paper

You are given a piece of paper that consists of $w \times h$ squares. You can cut the sheet in a vertical or horizontal axis at the positions with integer coordinates so that the paper becomes two ...
2
votes
1answer
39 views

A game relevant to sum and sequences.

We have a set of k positive integers $a_i$ and $x$ coins. A and B take turns picking up the coins so that the last picker is the winner. Each turn, one person can only pick up a positive number of ...
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 $...
0
votes
1answer
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 ...
3
votes
1answer
36 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, ...
1
vote
2answers
96 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 ...
1
vote
2answers
107 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 ...
0
votes
1answer
64 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 ...
1
vote
1answer
31 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 ...
5
votes
2answers
58 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 ...
1
vote
2answers
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$ ...
0
votes
1answer
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.
0
votes
1answer
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, ...
-1
votes
1answer
55 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 ...
0
votes
2answers
41 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 ...
1
vote
2answers
83 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 ...
0
votes
1answer
56 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 ...
0
votes
0answers
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 ...
3
votes
1answer
68 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 ...
1
vote
2answers
68 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 ...
0
votes
1answer
52 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 ...
5
votes
1answer
169 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 ...
1
vote
0answers
21 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)?
7
votes
1answer
94 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 ...
0
votes
1answer
62 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 ...
2
votes
0answers
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 ...
0
votes
1answer
80 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 ...
5
votes
0answers
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. ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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$. ...
1
vote
0answers
76 views

Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy?

Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one ...
1
vote
1answer
51 views

Quadratic Nimber Equation

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.
1
vote
1answer
68 views

The value of 2 person zero sum game described by square matrix.

I am trying to solve the following problem. Find the value of G, where G is a 2-person zero sum game described by an $n$ x $n $ square matrix A such that: $ -a_{ii} = \sum_{j \neq i} a_{ij} \\ a_{ij}...
2
votes
0answers
32 views

The smallest-sum game

The game is a function of an integer $n\geq 1$ and a number $t\in(0,n)$. An adversary picks $n$ numbers in $[0,1]$ whose total sum is $t$. You divide the numbers into two subsets and the adversary ...
3
votes
1answer
89 views

Each Player Removes a Number and All Its Divisors

Initially, the numbers $2,3,\ldots,n$ are written on a board. Alice and Bob alternately do the following: erase one number and all its divisors remaining on the board. The player who erases the last ...
3
votes
1answer
32 views

Counting $k$-sets with sum $n$ and xor-sum $0$.

Given $k, n > 0$, how many ordered lists $a_1, a_2, \dots, a_k$ are there such that $a_i \geq 0$ for all $i$, such that $\sum_i a_i = n$ and $\oplus_i a_i = 0$, where the latter operation denotes ...