pakhandi's blog

Game Theory : Approaching problems; Help
By pakhandi, history, 9 years ago, In English

I find problems of Game Theory a little hard to approach and mostly I even fail to prove a solution.
I was trying to do this question but I couldn't come up with any solution. Any help on this topic and question would be appreciated.
Thanks.
PS : I am reading about the Nim-Game on TopCoder..

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It has got nothing to do with graph theory and nim game. If you are familiar with N and P positions in a game, it might be handful. With some paperwork, one can observe that first k moves are losing positions and next l moves are winning positions and next k are losing and this pattern repeats. So each time game moves from winning to losing and vice versa. So number of moves will be 2*n/(k+l) + (n%(k+l)>=k) if both play optimally irrespective of whether they try to elongate game or not.

→ Reply