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
462 views

How to write induction proof of Sprague-Grundy function for subtration game?

So lets say that S={1,2,3} I find the sequence of Sprague-Grundy function. How do I justify my answer using induction?
0
votes
1answer
172 views

Subtraction Game

I recently read about the Nim Subtraction Game. I have a variant, Suppose you have N stones and two players Alice and Bob, who can choose to pick either 1 stones or K stones. If Alice plays first when ...
0
votes
1answer
55 views

Upper bound on number of starting positions of a grid coloring game

Let's play a game! The game has the following rules: Let $G$ be a $N\times N$ grid. To each grid square $(x,y)\in G$, assign either $true$ or $false$; call this mapping $C$ (that is, if $(x,y)$ is $...
0
votes
1answer
54 views

Interesting Probability Game With Uneven Return Scenarions

Let say we play a game. The game which spans the course of 5 trials. The game is as follows. You either receive 100 points or 40 points as a final payout. The only time a payout of a 100 points occurs ...
0
votes
0answers
84 views

Recursive core of coalition game

Can someone please explain the recursive core concept possibly with an example? http://arno.unimaas.nl/show.cgi?fid=5152 I don't understand how the recursion works. Thank you
0
votes
0answers
278 views

Mathematical reason for 2-player turn-based games

I've been reading Games, Puzzles, and Computation which analyzes games through game theory and complexity theory. The authors introduce something called "Constraint Logic" as a way of modeling games ...
0
votes
1answer
168 views

Applications of Scoring Play Combinatorial Game Theory

I'm currently looking into economic applications of scoring play combinatorial game theory. Details of the theory can be found in this paper. http://arxiv.org/abs/1202.4653 A friend of mine ...
0
votes
0answers
64 views

Can “proving mathematical theorems” as a 1 player puzzle be studied in combinatorial game theory?

In Combinatorial game theory other than 2 player games 1 player puzzle games are studied too. proving a mathematical theorem is a 1 player puzzle game. So I was curious to know whether it can be ...
0
votes
1answer
74 views

Question in discrete mathematics *

I have question. Can anyone able to explain to me this problem why if we have 5x the generating function $1+x^5+x^{10}+x^{15} + \ldots$ we have 5 is just constant and multiply with $x$ I know that $x$ ...
-1
votes
2answers
752 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 ...
-1
votes
1answer
69 views

Probability's Game

The game goes this way: There are 6 players, numered 1 to 6 (Player 1, Player 2,...,Player 6). Player 1 starts the game, he rolls a dice with six faces. If the result (x) of rolling the dice is 1 ...
-1
votes
1answer
75 views

What is the probability for …? [closed]

You start at the black field bottom left and have to move op til top right black field by only move right and up. What is the probability for moving over the white field with the cross in your way to ...
-1
votes
1answer
1k views

stable marriage problem doubt

Suppose we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might ...
-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 ...
-1
votes
2answers
799 views

Pick a number game theory

The scenario goes like this: You're in a group of 92 people. Each person picks a number from 0 to 100. Then the arithmetic mean is calculated from everyone's answers, and it is multiplied by 2/3. Then,...
-1
votes
1answer
65 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,...
-1
votes
1answer
512 views

Sprague–Grundy numbers

I would appreciate if someone can help me understand the columns of the table in this blog: http://lbv-pc.blogspot.co.uk/2012/07/treblecross.html . The author writes he leaves this as an exercise to ...
-2
votes
2answers
54 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. ...
-2
votes
1answer
51 views

Combinatorics in a restaurant

In a restaurant menu there are 6 types of drinks : Coca cola , lemonade , sprite , wine , tea and diet sprite . How many people need to order a drink to ensure that at least one drink would be ...
-2
votes
1answer
34 views

combinatorial game of sheets [closed]

We have an odd number of sheets organized in a pile. We have two players, and every player can remove $1,2,5$ or $6$ sheets, and keep them by their side. The winner is the player(s) that have even ...