Empty and Divide

There are two boxes. Initially, one box contains $m$ chips and the other contains $n$ chips. Such a position is denoted by $(m,n)$ , where $m>0$ and $n>0$ . Two players alternate moving. A move consists of emptying a box and equally divide the contents of the other between the two boxes with at least one chip in each box. Given that both players play optimally, how many starting positions $(m,n)$ , $1<m,n<1,000$ are there such that the first player can win?

Explicit Examples

• $(1,1)$ is a losing starting position. The first player cannot make any moves as it will leave one of the box empty after dividing.

• $(3,2)$ is a winning starting position. The first player empties the first box and leaves a position $(1,1)$ to the second player. Since no available moves exist for the second player, the first player wins by default.

Clarifications

• "equally divide the contents" means that the difference after the division must not be more than 1.