Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two players are playing a game. The game is played on a sequence of positive integer pairs. The players make their moves alternatively. During his move the player chooses a pair and decreases the larger integer in the pair by a positive multiple of the smaller integer in the pair in such a way that both integers in the pair remain positive. If two numbers in some pair become equal then the pair is removed from the sequence. The player who can not make any move loses (or in another words the player who encounters an empty sequence loses).

Given the sequence of positive integer pairs determine whether the first player can win or not (assuming that both players are playing optimally).

EXAMPLE : Let say we have N=2 i.e 2 pairs : (4,5),(5,6) Then in this If the first player choose to move (4,5) to (4,1) the second player will make it to (1,1). If the first player choose to move (5,6) to (5,1) the second player will make it to (1,1). So regardless of the move of the first player, the second will always win.

share|improve this question
    
Are you familiar with the Sprague-Grundy theorem? Each pair is a nim heap-you just have to figure out how big, then add them up nimwise –  Ross Millikan Jan 19 at 16:48
    
@RossMillikan could you please elaborate? –  user3001932 Jan 19 at 17:00
    
Do you know the game Nim? It is the prototype for impartial perfect information games. This is in that family. Each pair behaves just as a pile of stones in Nim. –  Ross Millikan Jan 19 at 17:04
    
@RossMillikan I know about Nim but how you are relating this problem to it am not getting it –  user3001932 Jan 19 at 17:06

1 Answer 1

This is an impartial perfect information game like Nim. We need to equate a pair $(a,b)$ with the size of the equivalent heap. A pair $(0,0)$ is an empty heap, so has value zero. A pair $(a,2a)$ is a size of $1$, as the only move is to $0$. Similarly, a pair $(a,na)$ is a heap of size $n-1$. $(3,2)$ is size zero, as it is a second player win-the only move is to $(3,1)$ and the second player moves to $(1,1)$ and wins. Similarly, $(n,n+1)$ is an empty heap. You need to find a formula for other pairs. The general rule is that any pair is the minimum value you can't move to.

share|improve this answer
    
Please explain by an example –  user3001932 Jan 19 at 17:54
    
what can you say about pair (n,n+2)? –  user3001932 Jan 19 at 18:04
    
What choices are there from $(n,n+2)$ for $n \ge 3?$ Then if $n$ is even, it has become a heap of size $\frac n2$. If $n$ is odd, $(2,3)$ is size zero, $(1,2)$ is size $1$, so it has become a heap of size $\frac {n-1}2$ Since $(n,n+2)$ cannot move to zero, it is size zero. –  Ross Millikan Jan 19 at 23:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.