Another Nim's Game Variant

Posted by Terry Smith on Stack Overflow See other posts from Stack Overflow or by Terry Smith
Published on 2013-11-03T09:50:45Z Indexed on 2013/11/03 9:53 UTC
Read the original article Hit count: 200

Filed under:

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 ?

© Stack Overflow or respective owner

Related posts about algorithm