A divisor-subtraction game where parity is only half the classification

pressF_17·Feb 27, 2026(edited)

Odd starting numbers look losing, but not every even number wins: 2 and 8 seem to lose as well. What is the pattern, and how can I prove it instead of extending a table? Problem: Players

A

and

B

play a game: given a positive integer

n

, one has to choose a divisor

m

n

which is greater than

1

and smaller than

n

and replace

n

with

n - m

. Player

A

makes the first move, players move alternately. The player who can't make a move loses the game. For which starting positive number

n

player

B

has a winning strategy? Source: Baltic Way 2013 · MNET-019Y

Open MNET-019Y in the question bank →

6 replies

snorlax_afk·Feb 27, 2026(edited)

For odd n, respond to the opponent's subtraction of m by subtracting the same m. It is still a legal proper divisor because m≤n/3, so m<n−m. After the pair of moves the number is odd and smaller.

pressF_17·Feb 28, 2026(edited)

So all odd positions are losing by induction. An even number with an odd proper divisor can move to an odd position and is winning.

snorlax_afk·Feb 28, 2026(edited)

Correct. The only even positions left are powers of two. From

2^k

, subtracting a power smaller than

2^{k-1}

lands at an even non-power of two, which is winning for the next player.

pixelated_toast·Feb 28, 2026(edited)

The one remaining move is subtraction of

2^{k-1}

, giving

2^{k-1}

. Thus the outcome alternates with k: k=1 loses, k=2 wins, k=3 loses, and so on.

pressF_17·Feb 28, 2026(edited)

Then B wins exactly for odd n and

n=2^{2r+1}=2\cdot4^r

. What about n=1?

snorlax_afk·Mar 1, 2026(edited)

It is included among the odd losing positions: A has no legal proper divisor to subtract. The game strictly decreases n, so the induction covers every play.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

A divisor-subtraction game where parity is only half the classification

pressF_17·Feb 27, 2026(edited)

Odd starting numbers look losing, but not every even number wins: 2 and 8 seem to lose as well. What is the pattern, and how can I prove it instead of extending a table? Problem: Players

A

and

B

play a game: given a positive integer

n

, one has to choose a divisor

m

n

which is greater than

1

and smaller than

n

and replace

n

with

n - m

. Player

A

makes the first move, players move alternately. The player who can't make a move loses the game. For which starting positive number

n

player

B

has a winning strategy? Source: Baltic Way 2013 · MNET-019Y

Open MNET-019Y in the question bank →

6 replies

snorlax_afk·Feb 27, 2026(edited)

For odd n, respond to the opponent's subtraction of m by subtracting the same m. It is still a legal proper divisor because m≤n/3, so m<n−m. After the pair of moves the number is odd and smaller.

pressF_17·Feb 28, 2026(edited)

So all odd positions are losing by induction. An even number with an odd proper divisor can move to an odd position and is winning.

snorlax_afk·Feb 28, 2026(edited)

Correct. The only even positions left are powers of two. From

2^k

, subtracting a power smaller than

2^{k-1}

lands at an even non-power of two, which is winning for the next player.

pixelated_toast·Feb 28, 2026(edited)

The one remaining move is subtraction of

2^{k-1}

, giving

2^{k-1}

. Thus the outcome alternates with k: k=1 loses, k=2 wins, k=3 loses, and so on.

pressF_17·Feb 28, 2026(edited)

Then B wins exactly for odd n and

n=2^{2r+1}=2\cdot4^r

. What about n=1?

snorlax_afk·Mar 1, 2026(edited)

It is included among the odd losing positions: A has no legal proper divisor to subtract. The game strictly decreases n, so the induction covers every play.