PUMaC 2022 · 组合（B 组） · 第 8 题
PUMaC 2022 — Combinatorics (Division B) — Problem 8
题目详情
- Fine Hall has a broken elevator. Every second, it goes up a floor, goes down a floor, or stays still. You enter the elevator on the lowest floor, and after 8 seconds, you are again on the lowest floor. If every possible such path is equally likely to occur, the probability you experience no a stops is , where a, b are relatively prime positive integers. Find a + b . b Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 2
解析
- Fine Hall has a broken elevator. Every second, it goes up a floor, goes down a floor, or stays still. You enter the elevator on the lowest floor, and after 8 seconds, you are again on the lowest floor. If every possible such path is equally likely to occur, the probability you experience no a stops is , where a, b are relatively prime positive integers. Find a + b . b Proposed by Adam Huang Answer: 337 Suppose there are u ups, d downs, and s seconds at which the elevator stays still. Since the elevator returns to its original height, u = d . Since 8 seconds elapse, u + d + s = 2 u + s = 8. 8 − s It is clear that s is even, so s ∈ { 0 , 2 , 4 , 6 , 8 } , and u = d = . We do casework based on the 2 value of s . Given a path with s stops, delete all seconds at which the elevator stays still to obtain a “reduced” path. The resulting path corresponds to a walk in the u - d plane by sending each up 8 − s 8 − s step to (1 , 0) and each down step to (0 , 1), such that the walk goes from (0 , 0) to ( , ) 2 2 without crossing the line u = d . The number of such paths is the Catalan number C 8 − s . Now, 2 we count how many ways there are to insert the stops into the path. Suppose we insert x i stops before the i -th move in the reduced path, as well as x after the last move. We must 9 − s count the number of solutions to x + . . . + x = s over the nonnegative integers. By stars 1 9 − s 8 and bars, this is . 8 − s We can explicitly compute that C = 1 , C = 1 , C = 2 , C = 5 , C = 14. Then, the total 0 1 2 3 4 P 8 number of possible paths is C 8 − s = 323. The number of paths with no s ∈{ 0 , 2 , 4 , 6 , 8 } 8 − s 2 4 8 stops is simply the term corresponding to s = 0, namely C = 14. It follows that the 4 8 14 desired probability is , so our answer is 323 + 14 = 337. 323 5