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 number of squares that he rolled. If his move ends on a square marked with an arrow, he moves his piece forward another s squares. If that move ends on an arrow, he moves another s squares, i i repeating 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 player 1 wins with probability strictly greater than . 2 Solution. The answer is k = 3 . Consider the configuration whose blank squares are 2, 6, and 10. Because these numbers represent all congruence classes modulo 3, player 1 cannot win on his first turn: he will come to rest on one of the blank squares. But player 2 will win on her first turn if she rolls 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 previously and now rolls a 1, ending up on square 6. Then player 2 will again have probability 1 / 2 of winning on 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 are two blank squares whose indices are incongruent modulo 3. Then player 1 wins on his first turn with probability only 1 / 3. If he does not win immediately, player 2 wins on her first turn with probability 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 with probability at least 1 / 3 + (2 / 3)(1 / 2)(2 / 3) = 5 / 9 > 1 / 2, as desired.