HMMT 十一月 2014 · GEN 赛 · 第 5 题
HMMT November 2014 — GEN Round — Problem 5
题目详情
- Mark and William are playing a game with a stored value. On his turn, a player may either multiply the stored value by 2 and add 1 or he may multiply the stored value by 4 and add 3. The first player 100 to make the stored value exceed 2 wins. The stored value starts at 1 and Mark goes first. Assuming 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 possible outcome given that the opponent is also playing optimally. If both moves lead to the same outcome, the player selects one of them arbitrarily.)
解析
- Mark and William are playing a game with a stored value. On his turn, a player may either multiply the stored value by 2 and add 1 or he may multiply the stored value by 4 and add 3. The first player 100 to make the stored value exceed 2 wins. The stored value starts at 1 and Mark goes first. Assuming 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 possible outcome 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 B affixes two 1s. The goal is to have greater than or equal to 101 1s. If any player makes the number of 1s in S congruent to 2 mod 3, then no matter what the other player does, he will lose, since the number of 1s 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 Mark does M ove A , and vice versa, which in total, affixes three 1s to S . This ensures that William always takes his turn while the number of 1s in S is congruent to 2 mod 3. Note that Mark has to follow this strategy because once he does not, then William can follow the same strategy and make Mark lose, a contradiction to the required optimal play. Since S starts out with one 1, this process gives William a maximum of 33 moves.