Two persons play the following game with positive integers. The initial number is . Each move consists of subtraction by an integer between and inclusive, or division by , rounding down when necessary. The player who obtains a non-positive integer wins. Who will win this game: the first player or the second?
, 2011
Solution
Though the problem is taken from the recent article (A. Guo. Winning strategies for aperiodic subtraction games // arXiv: 1108.1239v2), it could be known for the smaller numbers, say, for instead of .
The initial numbers for which the second player has a winning strategy are those ones that have odd numbers of trailing 's in base (i.e. if the biggest power of that divides is odd). The main difficulty of the problem is to invent this answer. The proof is trivial: each move of the first player makes this biggest power to be even, and after that the second player can make this power odd by a suitable move.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.