HMMT 二月 2002 · 团队赛 · 第 2 题
HMMT February 2002 — Team Round — Problem 2
题目详情
英文原题
- On each of his turns, player i rolls his die and moves his piece to the right by the numberof squares that he rolled. If his move ends on a square marked with an arrow, he moves hispiece forward another s squares. If that move ends on an arrow, he moves another s squares,
i irepeating until his piece comes to rest on a square without an arrow.
解析
英文解析
- there exists a board configuration with exactly k blank squares for which the second playerwins with probability strictly greater than .1
Solution. The answer is k = 3 . Consider the configuration whose blank squares are 2, 6, and 10.2
Because these numbers represent all congruence classes modulo 3, player 1 cannot win on his firstturn: he will come to rest on one of the blank squares. But player 2 will win on her first turn if sherolls a 1, for 2, 6, and 10 are all even. Thus player 2 wins on her first turn with probability 1 / 2.
Failing this, player 1 may fail to win on his second turn, for instance, if he rolled a 2 previouslyand now rolls a 1, ending up on square 6. Then player 2 will again have probability 1 / 2 of winningon her next turn. Thus player 2 wins the game with probability exceeding 1 / 2.
We must now prove that all configurations with fewer than three blanks favor player 1. If the numbers of the blank squares represent at most one residue class modulo 3, then clearly player
1 wins on his first turn with probability at least 2 / 3. This disposes of the cases of no blanks,
just one blank, and two blanks that are congruent modulo 3. In the remaining case, there aretwo blank squares whose indices are incongruent modulo 3. Then player 1 wins on his first turnwith probability only 1 / 3. If he does not win immediately, player 2 wins on her first turn withprobability at most 1 / 2, for there is a blank in at least one congruence class modulo 2. If player
2 does not win on her first turn, then player 1 wins on his second turn with probability at least
2 / 3, for there is only one blank square in front of him now. Thus player 1 wins the game withprobability at least 1 / 3 + (2 / 3)(1 / 2)(2 / 3) = 5 / 9 > 1 / 2, as desired.