返回题库

HMMT 二月 2018 · COMB 赛 · 第 6 题

HMMT February 2018 — COMB Round — Problem 6

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. Sarah stands at (0 , 0) and Rachel stands at (6 , 8) in the Euclidean plane. Sarah can only move 1 unitin the positive x or y direction, and Rachel can only move 1 unit in the negative x or y direction. Eachsecond, Sarah and Rachel see each other, independently pick a direction to move at the same time,
    and move to their new position. Sarah catches Rachel if Sarah and Rachel are ever at the same point.
    Rachel wins if she is able to get to (0 , 0) without being caught; otherwise, Sarah wins. Given that bothof them play optimally to maximize their probability of winning, what is the probability that Rachelwins?
解析

英文解析

  1. Sarah stands at (0 , 0) and Rachel stands at (6 , 8) in the Euclidean plane. Sarah can only move 1 unitin the positive x or y direction, and Rachel can only move 1 unit in the negative x or y direction. Eachsecond, Sarah and Rachel see each other, independently pick a direction to move at the same time,
    and move to their new position. Sarah catches Rachel if Sarah and Rachel are ever at the same point.
    Rachel wins if she is able to get to (0 , 0) without being caught; otherwise, Sarah wins. Given that bothof them play optimally to maximize their probability of winning, what is the probability that Rachelwins?
    Proposed by: Rachel Zhang
    Answer:63
    We make the following claim: In a game with n × m grid where n ≤ m and n ≡ m (mod 2), the 64
    probability that Sarah wins is under optimal play.1
    2 n
    Proof: We induct on n . First consider the base case n = 0. In this case Rachel is confined on a line,
    so Sarah is guaranteed to win.
    We then consider the case where n = m (a square grid). If Rachel and Sarah move in parallel directionsat first, then Rachel can win if she keep moving in this direction, since Sarah will not be able to catch
    Rachel no matter what. Otherwise, the problem is reduced to a ( n − 1) × ( n − 1) grid. Therefore, theoptimal strategy for both players is to choose a direction completely randomly, since any bias can beabused by the other player. So the reduction happens with probability , and by induction hypothesis 1
    1 12
    Sarah will with probability , so on a n × n grid Sarah wins with probability .
    n − 1 n
    2 2
    Now we use induction to show that when n < m , both player will move in the longer ( m ) directionuntil they are at corners of a square grid (in which case Sarah wins with probability . If Sarah 1
    2 nmoves in the n direction and Rachel moves in the m (or n ) direction, then Rachel can just move inthe n direction until she reaches the other side of the grid and Sarah will not be able to catch her.
    If Rachel moves in the n direction and Sarah moves in the m direction, then the problem is reducedto a ( n − 1) × ( m − 1) grid, which means that Sarah’s winning probability is now doubled to by 1
    n − 1
    induction hypothesis. Therefore it is suboptimal for either player to move in the shorter ( n ) direction.2
    This shows that the game will be reduced to n × n with optimal play, and thus the claim is proved.
    1 63
    From the claim, we can conclude that the probability that Rachel wins is 1 − = .
    2 646