, 2012

If $n$ is odd, the winner is Sara, no matter who starts. If $n$ is even, the winner is the one who does not start. Suppose at the end there are $p$ vertical and $r$ horizontal lines on the sheet of paper, where $p + r = n$. Then the sheet of paper is divided into $(p+1)(r+1)$ rectangles. If $n$ is odd, one of the numbers $p$ and $r$ is odd, hence $(p+1)(r+1)$ is even. In this case, Sara is the winner, no matter who starts and how they play the game.

Now suppose $n$ is even. Suppose after $n-1$ steps there are $s$ vertical and $t$ horizontal lines on the sheet of paper, where $s + t = n - 1$. Since $n-1$ is odd, numbers $s$ and $t$ must have different parities. After the last line is drawn, the sheet of paper is divided into $(s+1)t$ or $s(t+1)$ rectangles. Because $s$ and $t$ have different parities, the numbers $(s+1)t = st+t$ and $s(t+1) = st+s$ have different parities as well. The one who makes the last move may thus decide whether the final number of rectangles is odd or even. This player can win, no matter how the game has been played before. Since $n$ is even, the winner is the one who makes the last move, this is the one who does not start the game.