VIKRAM91's blog

By VIKRAM91, history, 21 month(s) ago, In English,

I was doing this problem on Spoj. The solution of this problem is that first player always wins.

Can anyone give me proof of this?

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Proof by contradiction :
Say the initial state is always a losing state. This means regardless of the number the first player picks , the second player ends up with a winning state (if not , the initial state would have been a winning state). Say the first player picks 1 and the second player ends up with {2,3,4,.....,N} which is a winning state. Say the second player picks X now and provides the first player with state S (a losing state) , the first player could have just picked X and forced the second player to state S ( a losing state) which is a contradiction. Hence the first player always wins.