# Tagged Questions

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.

27 views

### A question about interval operation result in a game

A state is:$A_{q}=(A_{q}^{0},...,A_{q}^{E})$ where $A_{i}^{j}$ is interval, $q$ and $E$ are positive integer The initial state is $A_{m}=((0,1),\emptyset...,\emptyset)$ , $m>E$ Procedure： Every ...
22 views

### Proving that problem of finding the winner in symmetrical game is in NP

Recently, I've stuck in quite an interesting problem. Here's its full description: Consider a connected, non-directed, weighted graph G. In some $v \in V(G)$ stays a chip. Two players are playing ...
21 views

### Probability of getting a “full house” by rolling dice [duplicate]

In poker, full house means getting three cards with the same rank, and another two cards with the same rank (not the same as other three cards). I can understand how to use combination to solve this ...
35 views

### Calculating the odds of winning a game

Problem: You, the user have 3 lives. In front of you are 5 cups - in each cup there is a piece of paper with 1 random number between 1 and 5 (inclusive) written on it. You must guess the number in ...
31 views

### Two guys pick from $n$ stones, the numbers of stones they can pick lie in a given set S. When the guy who pick first will win?

Alice and Bob take turns to pick stones from a pile of $n$ stones. Each number of stones they pick must lie in a given finite set $S\subset \mathbb{N}$. Who cannot pick will lose. If Alice picks first,...
524 views

### Optimal Solution

Players $1$ and $2$ are playing a game. They have a pile containing $N$ coins. Players take alternate turns, removing some coins from the pile. On each turn, a player can remove either one ...
114 views

### A variation of Nim game

There are two players X and Y . They write N integers on paper ( A_1 , A_2 , A_3 , .... A_N ). They have also p integers (b_1 , b_2 , b_3 , .... b_p ) . Now , Player X always takes turn first . He ...
103 views

### Mathematical game with numbers

We invented a mathematical game, which i am going to explain here. The first player choose a natural number, lets call it $n$ (if you play it for real, you must choose a sufficiently big number so ...
121 views

### Variation of Nim, where one has to divide a pile into any number of piles.

I am learning the basics of combinatorial game theory (impartial games). After learning about decompose a game into the sum of games, I feel comfortable with games that can divided into the sum of 1 ...
65 views

### Tic Tac Toe: What is the probability that a random player draws against an infallible player?

I have simulated a tournament between an infallible Tic Tac Toe player and one that chooses its moves randomly. Even after 5 million games, the infallible player wins every single game. I know that ...
90 views

### Position games: how to fill a matrix with dominos? [duplicate]

Dominos of size $2 × 1$ can be placed on a $m × n$ board so as to cover two squares exactly. Two players alternate placing dominos. The first one who is unable to place a domino is the loser. I can ...
48 views

### When can you win this directed graph game?

I am trying to consider the conditions under which you can win the following directed graph game: Directed graph game: At the start of the game, you are given a directed, acyclic graph $G$ with ...
238 views

### What is the optimal strategy in a game where players subtract 7 or add or divide by 2?

I made up a nim type game where players start with a relatively high number and then for each turn if the number is odd, the player either subtracts 7 from the number or alternately if the number is ...
21 views

### Find the Grundy number of the initial position and make the first move in a winning strategy for the following game

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game: In a pile there are two red balls, four green balls, four blue balls, and six ...
30 views

### Measure of Connectivity on a Chessboard

I'm programming a boardgame...game. The basic idea of it is there are two players (call them $X$ and $Y$) that are trying to trying to build a wall connecting the North and South, and East and West ...
32 views

### Check an algorithm to win hex as first player guaranteed

This question has more to do with the validity of the alogirthm than help per se. I'm unsure if this works with all board setups or just this one, or if it's valid at all. I'm going to start with a ...
123 views

### Solving the Gobblet game

In 1995 the Connect-4 Game was solved with a brute force approach. Using the standard 6 high / 7 wide grid, first player can force a win in 41 moves. Complexity of the Connect-4 game could be ...
12 views

### Is there an extension for sign expansion for any games?

A surreal number can be written as a sequence of $+$ and $-$, called the sign expansion. Is there something similar for any combinatorial games, supposedly with $+$, $-$ and some more symbols? If I ...
135 views

### A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
149 views

### Optimal Strategy for Card Split and Discard game

In a game of 2 players, there are 2 piles of cards. In every turn, a player has to discard one pile and divide the other into two equal parts (as close as possible). The game ends when a player is ...
35 views

### Define Grundy values

I want to helt to find out the grundy value to define a winning strategy for this game. Player 1 and 2 starts from position A where player 1 is the first one to move. The arrows show possibles ways ...
76 views

### Finding a Mathematical definition of a Discrete Time Game

Preface: Suppose we have a game world as depicted in the following figure: Where each of the white blocks is passable, And each of the black blocks is a wall and so impassable. Each of the Green ...
112 views

### Game: Group and Multi-Dimensional Chessboard

Let $G$ be a group and $S\subseteq G$. Consider a $d$-dimensional chessboard of size $n_1\times n_2\times \ldots \times n_d$, where $n_1,n_2,\ldots,n_d\in\mathbb{N}$. Each unit hypercube of the ...
54 views

### Candy Crush as an integer programming problem

I'm trying to model the basic version of a match-three game, where the player (has a maximum number of swaps) must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match ...
55 views

### Game of nim in which the number of heaps with odd coins is odd

Consider a Nim game in which the number of heaps with an odd number of coins is odd. Which player can guarantee a win and why? My idea is if the number of piles with an odd number of coins is odd ...
116 views

### Game: two pots with coins

Rules of the game with two players. First player puts any number of coins in the first pot. Then second player, knowing that number, puts any amount of coins in the second pot. Then they in turns (...
61 views

### Alice and bob xor nim game

Alice and Bob are playing a game. The rules of this game are as follows: Initially, there are $N$ piles of stones, numbered $1$ through $N$. The i-th pile contains $A[i]$ stones. The players take ...
137 views

### Misere nim, 2nd player winning strategy proof by induction

I'm having a problem with writing on paper things that I came up with. There's a Misere nim game with n stones, two players, every player can take 1, 2, 3 or 4 stones in one round, the one to remove ...
309 views

### Winning strategy of a game

The following is a game on monomials. Let $M(X,Y)$ denote the set of all monomials in $X$ and $Y$, i.e., $$M(X,Y)=\{X^aY^b\mid(a,b)\in\mathbb{N}^2\},$$ where $\mathbb{N}=\{0,1,\dots\}$. ...
222 views

### Determine optimal strategy in board game

We have a $25 \times 25$ board and two players. The fields of the board are numbered like this: From $0$ to $24$ from west to the east, and from $24$ to $0$ from north to the south. The first ...
212 views

### Finding p positions with 2 subtraction sets in the take-away game [closed]

Find the set of P-positions for the takeaway game with the subtraction sets: $S = {1,3,5,7}$ $S = {1,2,4,8,16,32}$ Who wins each game when there are 100 tokens on the table to start, the first or the ...
73 views

### Game, stealing edges in a graph.

I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows: Alice and Bob play a game. ...
28 views

### What does “1/2 positive advantage” mean in Hackenbush?

I'm currently reading "Winning Ways for Your Mathematical Plays" at http://annarchive.com/files/Winning%20Ways%20for%20Your%20Mathematical%20Plays%20V1.pdf. I'm on page 5, and I don't really ...
62 views

### Are all nimbers included in the surreals?

I guess the question says it all. The **nimber* (https://en.wikipedia.org/wiki/Nimber) concept, sometimes called "Sprague-Grundy numbers" embodies the "values" of positions in impartial games which ...
77 views

### Placing circles inside of a regular polygon.

Alice and Bob play the following game: on a table there is a regular $n$-gon. On each person's turn, they are required to place a circle of radius $r$ fully in the interior of the $n$-gon such that it ...
89 views

### How to find periodicity of a nim sequence?

I am trying to solve a problem which is a simple algorithmic game. Link to the problem - https://community.topcoder.com/stat?c=problem_statement&pm=6856 I have basically figured out that for ...
113 views

### Game-winning strategy

Player A and Player B are playing a turn-based game. At the beginning of the game there are $N(N \ge 3)$ points in a plane. In each turn one of the players chooses exactly $3$ different points and he ...
I'm thinking about a game theory problem related to factorization. Here it is, Q: two players A and B are playing this factorization game. At very first, we have a natural number $270000=2^4\times 3^... 1answer 84 views ### Polynomial game problem: do we have winning strategy for this game? I'm thinking about some game theory problem. Here it is, Problem: Consider the polynomial equation$x^3+Ax^2+Bx+C=0$. A priori,$A$,$B$and$C$are "undecided", yet and two players "Boy" and "Girl"... 1answer 44 views ### Nimber multiplication In the question on nimbers, the original poster asks for the meaning of Nimber multiplication in the context of impartial games. Edit: As noted by Mark Fischler in the comments below, the following ... 1answer 78 views ### What is the winning strategy for this Game on the Power Set Given a finite set, players alternately choose proper subsets. Once a subset has been chosen, none of its subsets may be chosen later. The last player to move wins. I figured out that, with optimal ... 1answer 161 views ### Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields? My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few ... 1answer 53 views ### Will cows win always if both play optimally? There is a green rectangular grid of size$n \times m$with$k$cows in it. The objective of the cow is to escape the field. If any one of the cows escape, all cows are set free. There is a farmer ... 1answer 263 views ### References on a game with white and black stones I'm looking for references on this game (name, strategies analysis, ...) : It's a two player game with two players (Black and White) A position of the game is a single line (sequence) of black and ... 1answer 31 views ### Switching balls among 3 piles There are 3 piles of balls. Each hour, I take a ball from one pile and move it to another. The amount of points I earn from this move is the amount of balls in the pile I took the ball from minus the ... 4answers 6k views ### Sharing a pepperoni pizza with your worst enemy You are about to eat a pepperoni pizza, which is sliced into eight pieces. Each pepperoni will unambiguously belong to some slice (no pepperoni is "between" slices). The caveat is that you have to ... 1answer 68 views ### Placing stones on vertices of polygon We have an$n$-gon with$n\geq 3$. Players$A$and$B$place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has ... 2answers 72 views ### Game with coloring squares in rectangular board Bob and Susan play a game on an$a\times b$board by alternating turns. In each turn, the player chooses a square comprising only uncolored cells, and color all of the cells. The first player who is ... 1answer 25 views ### Clarification in Siegel, combinatorial game theory On page$65$of Combinatorial Game Theory by Siegel, under the section of Dominated and Reversible Options, there is this part which I do not understand: Consider$G^{L_1R_1L}-G$. By assumption$G^{...
I'm starting to play around with some properties of combinatorial games, and I am having problems formalizing an argument based around the game of polite chocolate. There is an $n \times m$ grid of ...