HMMT 二月 2002 · 团队赛 · 第 9 题

英文解析

9. [30] In this problem suppose that s = s . Prove that for each board configuration, the first
   1 2
   player wins with probability strictly greater than .1
   Solution. Let σ and σ denote the sequence of the next twelve die rolls that players 1 and 22
   1 2
   respectively will make. The outcome of the game is completely determined by the σ . Now playeri
   1 wins in all cases in which σ = σ , for then each of player 2’s moves bring her piece to a square
   1 2
   already occupied by player 1’s piece. It is sufficient, therefore, to show that player 1 wins at leasthalf the cases in which σ 6 = σ . But all these cases can be partitioned into disjoint pairs
   1 2
   { ( σ , σ ) , ( σ , σ ) } ,
   1 2 2 1
   and player 1 wins in at least one case in each pair. For if player 2 wins in the case ( σ , σ ), say
   1 2
   on her n turn, the first n elements of σ do not take player 1 beyond space 12, while the first nthth 1
   elements of σ must take player 2 beyond space 12. Clearly, then, player 1 wins ( σ , σ ) on his n
   2 2 1
   turn.