HMMT 十一月 2025 · 冲刺赛 · 第 31 题
HMMT November 2025 — Guts Round — Problem 31
题目详情
- [17] Gumdrops come in 7 different colors. Mark has two boxes of gumdrops, each containing one gumdrop of each color. He repeats the following process 7 times: he removes one gumdrop uniformly at random from each box, then eats one of the two removed gumdrops uniformly at random and throws away the other. Compute the probability Mark eats one gumdrop of each color. n
解析
- [17] Gumdrops come in 7 different colors. Mark has two boxes of gumdrops, each containing one gumdrop of each color. He repeats the following process 7 times: he removes one gumdrop uniformly at random from each box, then eats one of the two removed gumdrops uniformly at random and throws away the other. Compute the probability Mark eats one gumdrop of each color. Proposed by: Jason Mao 1 Answer: 16 Solution 1: We consider the general problem where there are n different colored gumdrops. Without loss of generality, fix the order of gumdrops that Mark removes from the first box. There are n ! ways to arrange the order that Mark removes gumdrops from the second box with respect to the first, and n n 2 ways for Mark to decide the gumdrops that he eats, for a total of n ! · 2 possible combinations. © 2025 HMMT To count the scenarios in which Mark eats all different colored gumdrops, assume Mark eats k gumdrops n from the first box and n − k gumdrops from the second box. There are ways to select which k k colors of gumdrops from the first box are eaten. This uniquely determines the set of positions and colors of the n − k gumdrops that Mark must eat from the second box. As for ordering the colors in the second box, there are ( n − k )! ways to permute the eaten gumdrops and k ! ways to permute the n uneaten gumdrops. This is a total of · ( n − k )! · k ! = n ! ways Mark can eat n different colored k gumdrops for a given k . Since k can be any integer from 0 to n , the total number of ways is ( n + 1) · n ! = ( n + 1)!, so the probability that Mark eats n different colored gumdrops is ( n + 1)! n + 1 = . n n n ! · 2 2 1 For n = 7, this gives an answer of . 16 Solution 2: We consider the general problem where there are n different colored gumdrops. Label the gumdrop colors 1 , 2 , . . . , n , and suppose that gumdrop colored i from the first box is paired gumdrop colored σ ( i ) in the second box. We claim that condition on a fixed value of σ , the probability that Mark eats one gumdrop of each color c ( σ ) − n 2 k − 1 is 2 , where c ( σ ) is the number of cycles in σ . To see this, consider a cycle i, σ ( i ) , σ ( i ) , . . . , σ ( i ). Then in order for Mark to eat one gumdrop of each color, Mark has exactly two ways to eat the gumdrop of these colors: 2 • Eat all gumdrop of colors i, σ ( i ) , σ ( i ) , . . . from the first box. 2 • Eat all gumdrop of colors i, σ ( i ) , σ ( i ) , . . . from the second box. c ( σ ) Therefore, the number of ways for Mark to eat one gumdrop of each color is 2 . Thus, the claimed c ( σ ) probability is 2 . Therefore, the answer is X 1 c ( σ ) 2 , n 2 n ! σ ∈ S n where S is the set of all permutations of { 1 , 2 , . . . , n } . To evaluate the summation, we use the following n well-known lemma, which is a property of Stirling numbers of first kind. Lemma 1. For any n , we have X c ( σ ) x = x ( x + 1)( x + 2) . . . ( x + n − 1) . σ ∈ S n Proof. We use induction on n , with the base case n = 1 being clear. For the induction step, assume that the lemma is true for n − 1. We split an element σ ∈ S into two cases: n • If σ fixes n , then n is its own cycle, and we can remove n to get a permutation in S . Adding a n − 1 c ( σ ) lone cycle of n back multiply x by x , so by induction hypothesis, the contribution of this case is x · x ( x + 1)( x + 2) . . . ( x + n − 2) . • If σ does not fix n (i.e., n is a part of a cycle), then we remove n from the cycle and reglue the cycle by changing x → n → y to x → y . This gives a permutation in S . For each permutation n − 1 in S , there are n − 1 ways to insert n back, so the contribution of this case is n − 1 ( n − 1) · x ( x + 1)( x + 2) . . . ( x + n − 2) . Thus, the total sum is ( x + n − 1) · x ( x + 1)( x + 2) . . . ( x + n − 2) , completing the proof. © 2025 HMMT Plugging in x = 2 in the above lemma gives the answer 1 n + 1 · (2 · 3 · 4 · · · ( n + 1)) = , n n 2 n ! 2 1 and for n = 7, this evaluates to . 16 n