HMMT 二月 2019 · COMB 赛 · 第 6 题
HMMT February 2019 — COMB Round — Problem 6
题目详情
- 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 i chosen uniformly at random and independently for each i . What is the probability that P = P ? 8
解析
- 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 i chosen uniformly at random and independently for each i . What is the probability that P = P ? 8 Proposed by: Yuan Yao 1225 Answer: 16384 Solution 1. WLOG, AB and CD are horizontal line segments and BC and DA are vertical. Then observe that we can consider the reflections over vertical lines separately from those over horizontal lines, as each reflection over a vertical line moves P horizontally to point P , and vice versa. Now i i +1 consider only the reflections over horizontal segments AB and CD. Note that it is impossible for P 8 to be in the same location vertical location as P if there are an odd number of these reflections. Then 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 number of 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 sequences of 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 or z, 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 also k 3 if we consider only reflections over vertical line segments BC and AD. Now to finish, we only need to count the number of ways to combine 2 valid sequences of total length 4. This is ( ) 4 ∑ 8 a a , i 4 − i 2 i i =0 as there are a sequences of reflections over AB and CD, a sequences of reflections over BC and i 4 − i ( ) 8 AD such that there are 8 total reflections, and ways to choose which of the 8 reflections will be 2 i over 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 8 total sequences of reflections that place P at P. There are of course 4 = 65536 total sequences of 8 8 4900 1225 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 consider 0 a permutation of the lattice points on the coordinate plane, where all points with even x -coordinates are reflected across the y -axis and all points with even y -coordinates are reflected across the x -axis, so that the x - and y -coordinates are both rearranged in the following order: . . . , 4 , − 3 , 2 , − 1 , 0 , 1 , − 2 , 3 , − 4 , . . . . It is not difficult to see that a reflection across one of the lines corresponds to changing one of the coordinates from one number to either the previous number of the next number. Therefore, after the permutation, the question is equivalent to asking for the number of lattice walks of length 8 that returns to the origin. For such a lattice walk to return to origin, there needs to be the same number of up and down moves, and the same number of left and right moves. This condition is equivalent to 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 ( ) 2 8 suffices to designate four LU moves and four RU moves, giving = 4900 possible walks. Hence the 4 4900 1225 probability is = . 8 4 16384