VIKRAM91's blog

What is proof of spoj problem :- HUBULLU — Hubulullu
By VIKRAM91, history, 6 years 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

Comments Comments (2)
| Write comment?
»
6 years 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.

→ Reply