Stack Exchange Network

Stack Exchange network consists of 174 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.

2
votes
0answers
20 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 ...
-1
votes
0answers
24 views

What's the chance of the next person leaving a joint venture when a person before leaves? [closed]

A quite interesting practical question came to my mind today. I don't know whether it's solvable and I'll try to put everything as clearly as I can. Question: Say you have 9 friends and you are ...
1
vote
2answers
28 views

Count conditional probability of winning a game

In a certain game of tennis, Alice has a 60% probability to win any given point against Bob. The player who gets to 4 points first wins the game, and points cannot end in a tie. What is Alice's ...
3
votes
0answers
62 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
26 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
39 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 ...
0
votes
0answers
13 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
22 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
44 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
67 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
42 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
53 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
46 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
34 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
49 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
33 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
53 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
77 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
197 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
47 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
149 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
188 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
75 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
16 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
45 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 ...
0
votes
1answer
50 views

Dudo Game - Conditional Expectation

Say there are $n$ dice in the game. I have $p$ dice. Among them, I have $m_1$ aces and $m_2$ three. Let $X$ be the random variable: X="Number of dice which are either aces or three" and $B$ the event:...
1
vote
1answer
45 views

Non-terminating combinatorial games

The games I've come across thus far all have the property that their principal ideals are finite i.e the game terminates after finitely many moves so that the last position has the form {A|B} with (at ...
3
votes
1answer
75 views

Expected profit of my simple board game

How to play: Use 1 host and at least 1 player Each player has to toss fair six-sided dice to go to goal. If the player is at the 35th cell and tosses 2 or more, he can go to goal aa same as he ...
0
votes
1answer
41 views

Are there any examples of non-random games whose perfect-play outcome is proven but not solved?

My curiosity is inspired by the world-championship chess match of a couple days ago, when a supercomputer announced that mate-in-thirty-moves could be forced, but could not prove/explain it to humans ...
2
votes
1answer
51 views

Game involving taking exponent of a group until it becomes trivial.

Let $G \neq {1}$ be a finite group. Two players I $\&$ II, that know the group $G$ are playing the following game: Player I chooses a prime $p_1$ and then the players consider the group $G(p_1)):= ...
0
votes
1answer
65 views

Show that the first child can not win

Three children have 10 pieces numbered from 0 to 9 on both sides. They play the following game: -The first child chooses a piece, so a number, preserves it and passes the number on a sheet -The ...
2
votes
1answer
86 views

Proof that “$\uparrow$ is the unique solution of $tiny(G) = G$”

Tiny & miny games can be defined as: $$tiny(G) = \{0||0|-G\}$$ $$miny(G) = -tiny(G) = \{G|0||0\}$$ From the Wikipedia page for tiny and miny: Similarly curious, mathematician John Horton ...
1
vote
1answer
48 views

Proof one aspect of Nim game

Prove that if the Nim sum is not zero, then one of the piles is bigger than the Nim sum of the all the other piles. I've already proven that if the Nim sum of the piles is zero, then any one move ...
2
votes
3answers
126 views

A number game for two

Alice and Bob play the following number game. A target N is fixed, N being a positive integer. Alice then writes the number 1 on the blackboard. Bob responds with the number 2. Thereafter, at each of ...
3
votes
1answer
55 views

Distinction between “fuzzy” and “confused with.”

In the terminology of game theory, "fuzzy" and "confused with" signify different things. How are their associated concepts alike and distinct? EDIT: My initial encounter with the terms was here: ...
1
vote
0answers
56 views

Is there a solution to the stone game using the greedy method?

It’s a two player game. Both the players play optimally. Given n number of stones, a player can choose either 1 stone or p stones or q stones where 1 < p < q. Suppose player 'A' starts the game ...
2
votes
0answers
55 views

Queens on a torus chessboard.

Consider a Torus chessboard $\mathbb T$ of dimension $8\times8 $. How much queens it is possible to put on in such a way that no one attacks another? (I assume we use the same rules of standard ...
0
votes
0answers
26 views

Proof of Tartan's Theorem?

I have read only one proof online that shows that the Sprague-Grundy value of a position in an impartial game, denoted by say $g(x,y)$, is equal to $g_1(x) \otimes g_2(y)$, where $\otimes$ denotes Nim-...
1
vote
1answer
153 views

How to prove that for $n$ even and positive, the first player can guarantee a win?

Two players take turns placing dominoes on an $n \times 1$ board of squares, where each domino covers two squares and dominoes cannot overlap. The last player to play wins. (a) Where would ...
0
votes
1answer
36 views

What is the payoff function for games with more than two players?

For two player games, with payoff matrices $(A,B)$, let $x \in \Delta_x$ denote the mixed strategy of player $1$, and $y \in \Delta_y$ denote the mixed strategy of player $2$. Then the payoff ...
2
votes
1answer
54 views

Can the following Nim-like game be broken down into two parallel Nim sub-games (disjuctive sum)?

Say that there are two players, and two piles of chips. The first pile of chips has $m$ chips in it, where $m \geq 0$, but the second pile has exactly $1$ chip in it. The players alternate in taking ...
0
votes
0answers
54 views

How can I find the Sprague-Grundy function of this game?

The game involves N coins and a player can flip any consecutive $K$ sequence of coins, where $K$ is a perfect square. I have developed a function to list the values, but I am looking for a ...
0
votes
1answer
35 views

Impartial games: why is a game the disjunctive sum of its components?

Why is that for a game like Turning Turtles, the Sprague-Grundy value of a whole configuration $g$ is the disjunctive sum of its components with only one head? For example, $g(TTHTH) = g(TTH) + g(...
-2
votes
2answers
46 views

Unbiased coin game [closed]

Suppose Alice and Bob want to play a game sharing an unbiased coin. In her turn, Alice flips the coin only once. If she gets heads she sums one point, none otherwise. Then she hands the coin to Bob. ...
7
votes
2answers
54 views

Two-player game in $19$ rounds

Aashna and Radhika see the integers $1$ to $211$ written on a blackboard. They alternate turns and in every step each of them wipes out any $11$ numbers until only $2$ numbers are left on the ...
2
votes
2answers
88 views

A polytree game.

Starting from a directed star graph with $n$ nodes and all edges pointing away from the center, let two players alternate making one of the following moves: Tail move: $b \leftarrow a \rightarrow c \...
9
votes
1answer
79 views

Is multiplication of games that are equivalent to numbers well-defined?

It's well-known that if you take the definition of surreal multiplication and attempts to generalize it to all games, the result is not well-defined, in that it does not respect equivalence of games. ...
6
votes
0answers
53 views

Nim-Like Game: Subtracting powers of 2 from 1000. [duplicate]

A professor of one of my courses introduced us to a game to play during down-time, we start with 1000, then we take turns subtracting the powers of 2 (1 to 512), from 1000, we can use the same power ...
0
votes
0answers
66 views

What is the maximal value that we can have after 99 operations?

we begin with the numbers $1,\frac{1}2 ,\frac{1}3,\ldots \frac{1}{100}$ written in a board. We do the following operation : we delete $2$ numbers $a$ and $b$ from the board , and we remplace them with ...