Hosted by The Math Forum

# Subtract or Halve

Alice and Bob play a game. A positive integer starts the game and the players take turns changing the current value to a smaller one, and then passing the smaller one back to their opponent.

On each move, a player may subtract 1 from the integer, or halve it, rounding down if necessary. The person who first reaches 0 is the winner.

Alice goes first: she makes her choice of move on the starting value.

For example, starting at 15 a legal game (if not particularly well played) could be:

 Alice 15 → 7 Bob 7 → 6 Alice 6 → 3 Bob 3 → 1 Alice 1 → 0 Alice wins.

If the game starts with 1132, which player has a winning strategy?

Extra credit

1. Find a complete characterization of the numbers on which Alice wins.
2. What is the limiting probability that Alice wins on a random input (where we assume the input is random and less than n, and then let n approach infinity)?

Source: Mark Krusemeyer, Carleton College, who observes that it will likely appear in a forthcoming problem book, a successor to the Wohascum County Problem Book. It also appeared recently in the Buhler-Berlekamp problem column for MSRI's Emissary newletter.