Another Nim's Game Variant
- by Terry Smith
Given N binary sequence
Example :
given one sequence 101001 means
player 0 can only choose a position with 0 element and cut the sequence from that position {1,101,1010}
player 1 can only choose a position with 1 element ans cut the sequence from that position {null,10,101000}
now player 0 and player 1 take turn cutting the sequence, on each turn they can cut any one non-null sequence, if a player k can't make a move because there's no more k element on any sequence, he lose.
Assume both player play optimally, who will win ?
I tried to solve this problem with grundy but i'm unable to reduce the sequence to a grundy number because it both player don't have the same option to move. Can anyone give me a hint to solve this problem ?