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
1answer
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 ...
7
votes
0answers
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$...
1
vote
0answers
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, ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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" ...
2
votes
0answers
45 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
26 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
25 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
32 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
43 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
65 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
65 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
49 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
57 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
54 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
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, ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
2answers
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 ...
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
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 ...
0
votes
2answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
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
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
1
vote
0answers
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)?
7
votes
1answer
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 ...
0
votes
1answer
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 ...
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
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 ...
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
83 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
53 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.