HMMT 十一月 2014 · GEN 赛 · 第 5 题

英文解析

5. Mark and William are playing a game with a stored value. On his turn, a player may either multiplythe stored value by 2 and add 1 or he may multiply the stored value by 4 and add 3. The first playerto make the stored value exceed 2 wins. The stored value starts at 1 and Mark goes first. Assuming 100
   both players play optimally, what is the maximum number of times that William can make a move?
   (By optimal play, we mean that on any turn the player selects the move which leads to the best possibleoutcome given that the opponent is also playing optimally. If both moves lead to the same outcome,
   the player selects one of them arbitrarily.)
   Answer: 33 We will work in the binary system in this solution.
   General Test
   Let multiplying the stored value by 2 and adding 1 be M ove A and multiplying the stored value by 4
   and adding 3 be M ove B . Let the stored value be S . Then, M ove A affixes one 1 to S , while M ove Baffixes two 1 s. The goal is to have greater than or equal to 101 1 s. If any player makes the numberof 1 s in S congruent to 2 mod 3, then no matter what the other player does, he will lose, since the number of 1 s in S reaches 101 or 102 only from 99 ≡ 0 (mod 3) or 100 ≡ 1 (mod 3).
   Mark’s winning strategy: Do M ove A . In the succeeding moves, if William does M ove B , then Markdoes M ove A , and vice versa, which in total, affixes three 1 s to S . This ensures that William alwaystakes his turn while the number of 1 s in S is congruent to 2 mod 3. Note that Mark has to follow thisstrategy because once he does not, then William can follow the same strategy and make Mark lose, acontradiction to the required optimal play. Since S starts out with one 1, this process gives William amaximum of 33 moves.