HMMT 十一月 2018 · GEN 赛 · 第 9 题

HMMT November 2018 — GEN Round — Problem 9

20 players are playing in a Super Smash Bros. Melee tournament. They are ranked 1 − 20, and player n will always beat player m if n < m. Out of all possible tournaments where each player plays 18 distinct other players exactly once, one is chosen uniformly at random. Find the expected number of pairs of players that win the same number of games.

解析

20 players are playing in a Super Smash Bros. Melee tournament. They are ranked 1 − 20, and player n will always beat player m if n < m. Out of all possible tournaments where each player plays 18 distinct other players exactly once, one is chosen uniformly at random. Find the expected number of pairs of players that win the same number of games. Proposed by: Anders Olsen Answer: 4 Consider instead the complement of the tournament: The 10 possible matches that are not played. In order for each player to play 18 games in the tournament, each must appear once in these 10 unplayed matches. Players n and n + 1 will win the same number of games if, in the matching, they are matched with each other, or n plays a player a > n + 1 and n + 1 plays a player b < n. (Note no other pairs of 1 players can possibly win the same number of games.) The first happens with probability (as there 19 ( n − 1)(20 − n − 1) are 19 players for player n to be paired with), and the second happens with probability . 19 · 17 By linearity of expectation, the expected number of pairs of players winning the same number of games is the sum of these probabilities. We compute ( ) ( ) ( ) 19 18 19 ∑ ∑ 1 ( n − 1)(20 − n − 1) 1 n (18 − n ) 3