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.

4
votes
1answer
25 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
1answer
43 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$ ...
-1
votes
0answers
14 views

Color class and maximum independence set

It is true that very graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set Let G is a graph such that $C_1, C_2, ........
0
votes
1answer
28 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
30 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
50 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
36 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
1answer
60 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
50 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
48 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
65 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
1answer
35 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
51 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
157 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
12 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
89 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
59 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
23 views

Find the position for your maximize chance for winning. [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
58 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
56 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
107 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
28 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
23 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
52 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
48 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
53 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
87 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
30 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 ...
0
votes
2answers
42 views

How to make any natural numbers (placed in the chessboard cells) divisible by 10 by using the given tools [closed]

The original condition is: In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a ...
2
votes
0answers
19 views

A simple game with $n$ points in 3D space - red triangle wins

(Once again a son is torturing his father...) Alice and Bob play a fairly simple game with $n$ predefined points in 3D space. No four points are complanar (which also implies that no three points are ...
0
votes
1answer
26 views

Can anybody explain this extremely basic doubt in Combinatorial Game theory

I have a very basic doubt in Combinatorial Game theory. Whenever I am asked to find a strategy for somebody to win a game or to get the maximum sum or anything as such, what am I exactly supposed to ...
1
vote
2answers
49 views

Why does A always win in this game?

I have the following question with me: "A and B start with p = 1. Then they alternately multiply p by one of the numbers 2 to 9. The winner is the one who first reaches 1000. Who wins : A or B?" My ...
1
vote
1answer
68 views

Developing a strategy to win a game of picking elements from $S_n$

Given a integer $n>1$, Let $S_n$ be the group of permutations of the numbers $1,2,\dots n$. Two players, $A$ and $B$, play the following game. Taking turns, they select elements(one element at a ...
0
votes
1answer
52 views

What is the winning strategy for this problem?

Before the game starts, there are a few "points" on the desktop, and then the two players take turns to do the following operations until the operation can not be completed: Starting from a "point" ...
0
votes
1answer
56 views

How to give a winning strategy for this game?

I have the following question with me: "Start with several piles of chips. Two players move alternately. A move consists in splitting every pile with more than one chip in two piles. The one who ...
45
votes
3answers
3k views

Prime number construction game

This is a variant of Prime number building game. Player $A$ begins by choosing a single-digit prime number. Player $B$ then appends any digit to that number such that the result is still prime, and ...
1
vote
1answer
107 views

Finding the winning strategy of a variation of the Nim game

Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this: The games starts with 16 stones arranged as follow: o (first pile) ooo (second pile) ...
0
votes
1answer
51 views

Using factorials to calculate # of chess combinations

I recently came across a coding problem in which the solution involves writing a program that can take in the starting position and destination square of a chess piece, and then output the number of ...
0
votes
2answers
74 views

Odds of the perfect game of bingo.

Playing breaking bingo. The last round is a jackpot round where the caller calls seven balls containing at least a B, I, G, and O. (The freespace provides the N if no N is called). To win the Jackpot, ...
1
vote
1answer
39 views

combinatoric problem: probability of different wins (outcomes) in the some way similar to the the BINGO game

In game, we randomly generate four grids (cards) $3\times 5$ (row × col), with each column containing 3 numbers randomly selected without replacement from 18 possibilities: first columns from ...
3
votes
1answer
82 views

Looking for solution to “lights out” puzzle variant with multiple states

Recently in World of Warcraft, there is a puzzle that is very similar to the "lights out" puzzle where a player needs to flip switches to turn all the lights into a specific color (in this case yellow,...
5
votes
1answer
88 views

Optimizing a winning strategy for a quick tabletop game

A friend of mine recently shared the following puzzle with me: Puzzle: A circular turntable is divided into four congruent quadrants by two perpendicular lines. (Think of a circle in the $xy$-...
5
votes
2answers
210 views

What is actually happening in the Hackenbush advantage measurement?

I'm reading Berlekamp/Conway/Guy's Winning Ways for Your Mathematical Plays. Here: I am a little bit confused: What is happening here? It seems to me that we know that a game with a unique red edge ...
3
votes
4answers
50 views

Number of moves required to empty all the boxes as per the given rules

I have the following question with me: "There are 1990 boxes containing 1,2,3,....,1990 chips respectively, on a table. You may choose any subset of boxes and subtract the same number of chips from ...
2
votes
2answers
172 views

Find elements from xor relations

Alice and Bob are playing a game. Alice has a sequence of positive integers $$a_1,a_2, \ldots, a_N;$$ Bob should find the values of all elements of this sequence. Bob may ask Alice at most $N$ ...
8
votes
1answer
247 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-...
1
vote
0answers
77 views

King of the Centre - Is this an existing game?

Consider an $n$-player infinitely repeated game. First stage nature chooses for each player, $i$, a radius $r_{i}$. For each later stage $t$ each player $i$: The payer chooses a "target" $p_{i, t}$...
0
votes
0answers
21 views

Definition of a Downward Closed Feasible Set Single Parameter Environment (Game Theory)

Could someone give more clarification on what a downward closed feasible set? So we have a Single Parameter Environment with feasible set X. The definition given is: subsets of a feasible set are ...
1
vote
0answers
54 views

Nash equilibrium in antagonist game in a 2x5 matrix

Background Input matrix: $$ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 4 & 3 & 2 \\ \end{bmatrix}$$ We have a game with 2 players. The game is antagonistic e.g ...