返回题库

HMMT 二月 2019 · COMB 赛 · 第 6 题

HMMT February 2019 — COMB Round — Problem 6

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

题目详情

英文原题

  1. A point P lies at the center of square ABCD . A sequence of points { P } is determined by P = P ,
    n 0
    and given point P , point P is obtained by reflecting P over one of the four lines AB, BC, CD, DA ,
    i i +1 ichosen uniformly at random and independently for each i . What is the probability that P = P ? 8
解析

英文解析

  1. A point P lies at the center of square ABCD . A sequence of points { P } is determined by P = P ,
    n 0
    and given point P , point P is obtained by reflecting P over one of the four lines AB, BC, CD, DA ,
    i i +1 ichosen uniformly at random and independently for each i . What is the probability that P = P ?
    Proposed by: Yuan Yao 8
    1225
    Answer:
    16384
    Solution 1. WLOG, AB and CD are horizontal line segments and BC and DA are vertical. Thenobserve that we can consider the reflections over vertical lines separately from those over horizontallines, as each reflection over a vertical line moves P horizontally to point P , and vice versa. Nowi i +1
    consider only the reflections over horizontal segments AB and CD. Note that it is impossible for Pto be in the same location vertical location as P if there are an odd number of these reflections. Then 8
    we consider the reflections in pairs: let w denote reflecting twice over AB, let x denote reflecting over
    AB and then CD, let y denote reflecting over CD and then AB, and let z denote reflecting twice over
    CD. Note that both w and z preserve the position of our point. Also note that in order to end at the same vertical location as P, we must have an equal number of x ’s and y ’s. Now we count the numberof sequences of length at most 4 with this property:
    • Case 1: Length 0
    There is just the empty sequence here, so 1.
    • Case 2: Length 1
    There are just the sequences w and z, so 2.
    • Case 3: Length 2
    We may either have an x and a y or two characters that are either w or z. There are 2 sequencesof the former type and 4 of the latter, for 6 total.
    • Case 4: Length 3
    There are 12 sequences with an x, a y, and either a w or a z, and 8 sequences of only w ’s and z ’s,
    for 12 total.
    • Case 5: Length 4
    There are 6 sequences of 2 x ’s and 2 y ’s, 48 with one of each and two terms that are either w orz, and 16 of just w ’s and z ’s, for a total of 70.
    Now let the number of such sequences of length k be a (so a = 20). Note that these counts work alsok 3
    if we consider only reflections over vertical line segments BC and AD. Now to finish, we only need tocount the number of ways to combine 2 valid sequences of total length 4. This is
    ( )
    ∑4
    a a ,8
    i 4 − i
    2 ii =0
    as there are a sequences of reflections over AB and CD, a sequences of reflections over BC andi 4 − i
    ( )
    AD such that there are 8 total reflections, and ways to choose which of the 8 reflections will be 8
    2 iover AB or CD. We compute that this sum is 1 · 70 · 1 + 2 · 20 · 28 + 6 · 6 · 70 + 20 · 2 · 28 + 70 · 1 · 1 = 4900
    total sequences of reflections that place P at P. There are of course 4 = 65536 total sequences of 88
    4900 12258
    reflections, each chosen uniformly at random, so our answer is = .
    65536 16384
    Solution 2. Suppose that P is the origin and the four lines are x = ± 0 . 5 and y = ± 0 . 5. We considera permutation of the lattice points on the coordinate plane, where all points with even x -coordinates 0
    are reflected across the y -axis and all points with even y -coordinates are reflected across the x -axis, sothat the x - and y -coordinates are both rearranged in the following order:
    It is not difficult to see that a reflection across one of the lines corresponds to changing one of thecoordinates from one number to either the previous number of the next number. Therefore, afterthe permutation, the question is equivalent to asking for the number of lattice walks of length 8 thatreturns to the origin. For such a lattice walk to return to origin, there needs to be the same numberof up and down moves, and the same number of left and right moves. This condition is equivalentto having four moves that are left or up (LU), and four moves that are right or up (RU). Moreover,
    knowing whether a move is LU and whether it is RU uniquely determines what the move is, so it
    ( )
    suffices to designate four LU moves and four RU moves, giving = 4900 possible walks. Hence the 82
    4900 12254
    probability is = .
    4 163848