Impartial games problems

Again with a new problem, but this time i will explain a very nice approach to solve a specific set of problems located under the category of game theory.

Impartial games

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.

Impartial games include Nim, Sprouts, Kayles, Quarto, Cram, Chomp, and poset games. I will explain the nim problem and how to solve it, then i will move to the Stone Piles problem that i solved this week.

 

Nim Problem

Nim is a game in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and no more than a set maximum number from the heap.

An example normal play game is shown below:

A B C
3 4 5 I take 2 from A
1 4 5 You take 3 from C
1 4 2 I take 1 from B
1 3 2 You take 1 from B
1 2 2 I take entire A heap leaving two 2’s.
0 2 2 You take 1 from B
0 1 2 I take 1 from C leaving two 1’s.
0 1 1 You take 1 from B
0 0 1 I take entire C heap and win.

What is your winning strategy? 

Luckily, we can find one. Nim has been solved for all starting positions and for any number of heaps. First we’ll look at different types of game positions, then we’ll do some work with “nimbers” (yes, that really is a word) and then apply them to finding a solution to Nim.

Types of impartial game positions

• A game is in a P-position if it secures a win for the Previous player (the one who just moved).
• A game is in a N-position if it secures a win for the Next player.

So in normal play Nim with three heaps, (0,0,1) is an N-position and (1,1,0) is a P-position. We call the position from which no possible moves are left a terminal position. To find whether a Nim position is N or P, we work backwards from the end of the game to the beginning in a process called backwards induction:

1. Label every terminal position as P.
2. Label every position that can reach a P position as N.
3. For positions that only move to N positions, label P.
4. At this point either all positions are labeled or return to step 2 and repeat the process until all positions are labeled.

Applying these rules to Nim, we first set the only terminal position (in other games there could be many) 0,0,0, to P. It is obvious that any position (0,0,n) is an N position, since the next player can just take the last heap in one turn.

Nimber arithmatic

The key operation in the solution to Nim is binary addition without carrying. To add two numbers in this manner, first write out their binary expansions, and then take the exclusive or (XOR) of the two numbers bit by bit.

Theorem 1. A position, (x1, x2, x3), in Nim is a P-position if and only if the nim-sum of its components is zero, x1 ⊕ x2 ⊕ x3 = 0. As an example, take the position (x1, x2, x3) = (13, 12, 8). Is this a P-position? If not, what is a winning move? We compute the nim-sum of 13, 12 and 8:
 

13 = 11012
12 = 11002
8 = 10002
nim-sum = 10012 = 9
 

Since the nim-sum is not zero, this is an N-position according to Theorem 1. Can you find a winning move? You must find a move to a P-position, that is, to a position with an even number of 1’s in each column. One such move is to take away 9 chips from the pile of 13, leaving 4 there. The resulting position has nim-sum zero:

4 = 1002
12 = 11002
8 = 10002
nim-sum = 00002 = 0

Another winning move is to subtract 7 chips from the pile of 12, leaving 5. Check it out.

Now we can solve the Nim game with any number of piles.

Stone Piles problem

This is a much harder problem in which we are going to move to another theorem called Sprague Grundy theorem, in which will help us solving this problem.

You can view this problem at interviewstreet.com using this link. However in this problem the game described as below:

There are N piles of stones where the ith pile has x_i stones in it. Alice and Bob play the following game:

• a. Alice starts, and they alternate turns.

• b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 

• c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Sprague Grundy Theorem

Definition: A directed graph G(X,F) Where A directed graph, G, is a pair (X,F) where X is a nonempty set of vertices (positions) and F is a function that gives for each x ∈ X  a subset of X, where each of them is a position reachable from x.

The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-negative integer values, such that g(x) =min{n ≥ 0 : n = g(y) for y ∈ F(x)}.

In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x. If we define the minimal excludant, or mex, of a set of non-negative integers as the smallest non-negative integer not in the set, then we may write simply g(x) =mex{g(y) : y ∈ F(x)}.

Mex means Minimum Excluded Value. Below are some practice examples:

mex({2,4,5,6}) = 0
mex({0,1,2,6}) = 3

Now how to solve the stone piles game?

1. Mark all terminal nodes sg = 0 (In this case its 1 and 2 as the player will not be able to divide them)

2. For each pile compute the sg value of it

3. Get the nim-sum of all the sg values of the piles, if 0 then BOB wins, else ALICE wins.

How to get the sg value of a number?

1. DFS all the possible divisions of this pile

2. Recursively compue the sg values of all the possible divisions

3. Return the mex out of them

Now i am done explaining the whole topic, i think its really interesting and i suggest you solving more problems as i will do isA.

Matrix exponentiation to solve linear recurrence

The last weekend i was trying to solve a problem called Circle Summation on interviewstreet.com, if you have account you can view it using this link. However the problem is that we have N children sitting along a circle, numbered 1,2,...,N clockwise. The i^th child has a piece of paper with number a_i written on it.  They play the following game:

In the first round, the child numbered x adds to his number the sum of the numbers of his neighbors. In the second round, the child next in clockwise order adds to his number the sum of the numbers of his neighbors, and so on. The game ends after M rounds have been played.

Given N, M, and X's, Formulate the following output:

Output N lines each having N integers. The j^th integer on the i^th line contains the number that the j^th child ends up with if the game starts with child i playing the first round. Output a blank line after each test case except the last one. Since the numbers can be really huge, output them modulo 1000000007.  

As you can see we can represent this problem as a linear recurrence where F(N) = F(N-1) + F(N) + F(N+1).

A linear recurrence is a sequence of numbers, in which we can compute the nth term from the existent of other terms (e.g., Fibonacci sequence).

For example in the fibonacci series we can represent the sequence using the following recurrence equation:

Where 

Now by looking into the following recurrence we can represent it with this equation x_i+1 = Mx_i, for some constant matrix M.

| f(n+1) | = | 1 1 | x | f(n)   |
| f(n)   |   | 1 0 |   | f(n-1) |        => (1)

From (1) We can see that we can find F(N), by solving M^n. (Prove it, using math induction).

By analyzing the previous equation we can find that we will do O(M^3) operations for matrix multiplication where M is a very small number, and for the power function we can do it in O(Log(N)) operations, that will lead us to O(M^3 Log(N)) to solve fibonacci numbers.

Now, Can you solve the circle summation problem? :).. I solved it..

Number of positive integral solutions for an equation

In this post i will explain my solution for a very nice mathematical problem. If you have an account on interviewstreet, you can view it using this link EQUATIONS. However in this problem you have the following equation (1/X) + (1/Y) = 1/N! and N is given, And you have to find all the valid pairs of X, and Y that solve this problem.

One can say that the simplest way is to iterate through all possible Xs, and Ys checking the pairs that solve the equation. But what if N is equal 10^6 for example?.

First lets define M = N!, then we have:

1x+1y=1N!=1M

Lets also define that X = M+a and Y = M+b. where (a, b) could be positive or negative numbers, then we have:

⇒2M+a+b(M+a)(M+b)=1M

We can solve the above equation and we will get the following:

2M2+M(a+b)=M2+M(a+b)+ab

⇒M2=ab

Now look at all the divisors of M2=(N!)2 and find the values of a and b and hence find the values of x and y.

So we need to know how many divisors (N!)^2 have. As you may know that the number of divisors of a number equals the result of multiplying the exponents of the prime factors of this number.
So    
So if we have n = a^x * b^y * c^z, where (a, b, c) are the prime factors of n, then the number of divisors of n = (x+1)*(y+1)*(z+1), I hear you asking why?

As you can see that all the divisors of n are multipliers of the prime factors of n.

So a could be chosen (x+1) times (0, 1, 2, ... x) times,
b could be chosen (y+1) times (0, 1, 2, .... y) times,
c could be chosen (z+1) times (0, 1, 2, ... z) times.

Now you have all the ideas that make a solution, show me your skills :)