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.