Problem 10


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 = 2km where k > 1 and m is odd.  If k = 2r +1 is odd, then the first player should reduce  n to n –1 = 2km = 22r+1m.  If k = 2r+ 2 is even, then the first player’s move is to reduce n to (n-1)/2 = 2k-1m = 22r+1m, yielding the same result.  At this point, the moves are forced for a while.  The second player must reduce 22r+1m to 22rm, and the first player reduces to 22r-1m, etc.  After 2r+1 moves, the second player finally reduces the number to the odd integer m and the procedure now repeats.