HMMT 十一月 2022 · THM 赛 · 第 10 题
HMMT November 2022 — THM Round — Problem 10
题目详情
- There are 21 competitors with distinct skill levels numbered 1 , 2 , . . . , 21. They participate in a ping- pong tournament as follows. First, a random competitor is chosen to be “active”, while the rest are “inactive.” Every round, a random inactive competitor is chosen to play against the current active one. The player with the higher skill will win and become (or remain) active, while the loser will be eliminated from the tournament. The tournament lasts for 20 rounds, after which there will only be one player remaining. Alice is the competitor with skill 11. What is the expected number of games that she will get to play?
解析
- There are 21 competitors with distinct skill levels numbered 1 , 2 , . . . , 21. They participate in a ping- pong tournament as follows. First, a random competitor is chosen to be “active”, while the rest are “inactive.” Every round, a random inactive competitor is chosen to play against the current active one. The player with the higher skill will win and become (or remain) active, while the loser will be eliminated from the tournament. The tournament lasts for 20 rounds, after which there will only be one player remaining. Alice is the competitor with skill 11. What is the expected number of games that she will get to play? Proposed by: Zixiang Zhou 47 Answer: 42 Solution 1: Insert a player with skill level 0, who will be the first active player (and lose their first game). 10 If Alice plays after any of the players with skill level 12 , 13 , . . . , 21, which happens with probability , 11 then she will play exactly 1 game. 1 If Alice is the first of the players with skill level 11 , 12 , . . . , 21, which happens with probability , 11 10 then there are an expected players between her and someone better than her. Thus, she plays an 12 10 17 expected 2 + = games. 12 6 Alice will only play the player with skill 0 if she is the first of all other players, which happens with 1 probability . 21 The final answer is 10 1 17 1 47 · 1 + · − = . 11 11 6 21 42 n +1 1 Solution 2: Replace 21 by n and 11 by k . The general formula is + 1 − − [ k = n ]. ( n − k +1)( n − k +2) n The problem is roughly equivalent to picking a random permutation of 1 , . . . , n and asking the expected number of prefix maximums that are equal to k . For the first m elements, the probability is equal to P (max of first m = k ) = P (max of first m ≤ k ) − P (max of first m ≤ k − 1) k k − 1 · m ! · ( n − m )! · m ! · ( n − m )! m m = − n ! n ! k k − 1 m m = − n n m m k − 1 m − 1 = n m so k − 1 k X m − 1 E [prefix max = k ] = n m m =1 k X ( k − 1)! m !( n − m )! = ( k − m )!( m − 1)! n ! m =1 k X ( k − 1)! m ( n − m )! = n ! ( k − m )! m =1 k X ( k − 1)!( n − k )! n − m = m n ! n − k m =1 Now a combinatorial interpretation of the sum is having n balls in a row, choosing a divider between them, and choosing 1 ball on the left side of the divider and n − k balls on the right side of the divider ( m corresponds to the number of balls left of the divider). This is equal to choosing n − k + 2 objects n +1 among n + 1 objects and letting the second smallest one correspond to the divider, which is . n − k +2 Therefore the answer is ( k − 1)!( n − k )! ( n + 1)! n + 1 · = . n ! ( n − k + 2)!( k − 1)! ( n − k + 1)( n − k + 2) We need to do some more careful counting to address the game lost by person k and to subtract 1 1 game for the event that person k is the first person in the permutation. This yields the 1 − − [ k = n ] n term. The numbers 21 and 11 are chosen so that the answer simplifies nicely.