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.
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.