HMMT 二月 2026 · 冲刺赛 · 第 20 题
HMMT February 2026 — Guts Round — Problem 20
题目详情
- [11] Derek is at the front of a line, with six clones named Derek #1 , Derek #2 , Derek #3 , Derek #4 , Derek #5 , and Derek #6 standing behind him in a uniformly random order. For all positive integers k th between 1 and 6 , inclusive, on the k minute from now, Derek # k will swap positions with whoever is standing directly in front of him in the line. Compute the probability that after 6 minutes, Derek is still at the front of the line. ©2026 HMMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2026, February 14, 2026 — GUTS ROUND Organization Team Team ID#
解析
- [11] Derek is at the front of a line, with six clones named Derek #1 , Derek #2 , Derek #3 , Derek #4 , Derek #5 , and Derek #6 standing behind him in a uniformly random order. For all positive integers th k between 1 and 6 , inclusive, on the k minute from now, Derek # k will swap positions with whoever is standing directly in front of him in the line. Compute the probability that after 6 minutes, Derek is still at the front of the line. Proposed by: Srinivas Arun 53 Answer: 144 Solution 1: Let a be the answer to the problem if there are n total people in the line. We wish to n find a . 7 The key observation is that once Derek #1 swaps positions with the person in front of him, the actions of all people standing behind Derek #1 become irrelevant, as they cannot swap with anyone in front of Derek #1. Using this observation, we compute a recursively as follows: n 1 • There is a chance that Derek #1 starts at the 2nd position. In this case, since Derek is not n − 1 at the front after the first swap and never moves forward, the probability Derek remains at the front is 0 . 1 • There is a chance that Derek #1 stars at the 3rd position. In this case, after Derek #1 n − 1 swaps, we can ignore him and everyone behind him, which leaves one person, so the probability Derek remains at the front is a . 1 1 • There is a chance that Derek #1 starts at the 4th position. In this case, after Derek #1 n − 1 swaps, we can ignore him and everyone behind him, which leaves two people, so the probability Derek remains at the front is a . 2 • . . . 1 • There is a chance that Derek #1 starts at the last position. In this case, after Derek #1 n − 1 swaps, we can ignore him and everyone behind him, which leaves n − 2 people, so the probability Derek remains at the front is a . n − 2 ©2026 HMMT 1 Thus, we get a = ( a + · · · + a ) . Using a = 1 and a = 0 , we can recursively compute n 1 n − 2 1 2 n − 1 1 1 a = (1) = , 3 2 2 1 1 a = (1 + 0) = , 4 3 3 ( ) 1 1 3 a = 1 + 0 + = , 5 4 2 8 ( ) 1 1 1 11 a = 1 + 0 + + = , 6 5 2 3 30 ( ) 1 1 1 3 53 a = 1 + 0 + + + = . 7 6 2 3 8 144 (Computing a can be skipped.) 6 Solution 2: We say Derek# i has label i , and let j be the largest positive integer for which the first j clones (not including Derek himself) have labels in descending order. Claim 1. Derek stays at the front of the line if and only if j is even. Proof. We proceed with induction on j . Base case: j = 1 . The clone right behind Derek will swap with Derek before anyone else can swap with that clone, ensuring Derek ends up not in the front. Induction Step: Assume the claim holds for j − 1 . Let D denote whichever clone is right behind Derek, and observe that there are j − 1 clones after D with labels in descending order who all swap before D , with the last of them swapping before anyone else can swap with him (since j is maximal). After those j − 1 clones have made their swaps, by the induction hypothesis, • if j is even, j − 1 is odd, so D is no longer right behind Derek. Whoever is right behind Derek has already made their swap, so Derek will remain in the front of the line. • if j is odd, j − 1 is even, so D is still right behind Derek and will swap with him, ensuring Derek ends up not in the front. This completes the proof. The probability that j is at least m is the probability that the first m people are in descending order, or 1 /m ! . Thus, for m < 6 , the probability that j = m is 1 /m ! − 1 / ( m + 1)! . We conclude the answer is 1 1 1 1 1 53 − + − + = . 2! 3! 4! 5! 6! 144 Remark. Remark: A generalized version of this solution shows that the desired probability with n clones equals the probability that a uniformly random permutation on n elements is a derangement, i.e., no element ends up in its original spot.