** **

An interesting 2 – person game starts with a randomly chosen
positive integer. The two players then
take turn decreasing the integer according to the following rule. Suppose that the integer has already been
modified so that it is now equal to *n. * If *n* is even, then the player must change it to *n*/2. On the other hand, if *n *is odd, then
the player can change it to either *n – *1 or (*n –* 1)/2. The player to reach 0 first is the
winner. Show that, if the starting
positive integer is odd, then the first player to move can always win. .
[Problem submitted by Iris Magee, LACC Instructor of Mathematics.
Source: Pomona-Wisconsin Mathematical Talent Search.]

**Solution for Problem 10:**

We will show that the first player can guarantee that the second player always gets an even integer to reduce. Thus the second player never gets the number 1, which is the only integer that can be reduced to 0 in a single move.

Suppose it is the first player’s move and that the modified
integer *n *is odd. If *n* =
1, then the player reduces this to 0 in a single move. On the other hand, if *n* >1, then *n*
– 1 is a positive even integer, so we can write *n* – 1 = 2^{k}*m*
where k __>__ 1 and *m* is odd.
If k = 2r +1 is odd, then the first player should reduce *n *to *n –*1 = 2^{k}*m*
= 2^{2r+1}m. If k = 2r+ 2 is
even, then the first player’s move is to reduce *n* to (*n*-1)/2 = 2^{k-1}*m*
= 2^{2r+1}m, yielding the same result.
At this point, the moves are forced for a while. The second player must reduce 2^{2r+1}*m*
to 2^{2r}*m*, and the first player reduces to 2^{2r-1}*m*,
etc. After 2r+1 moves, the second
player finally reduces the number to the odd integer *m* and the procedure
now repeats.