返回题库

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

HMMT November 2018 — GEN Round — Problem 9

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 20 players are playing in a Super Smash Bros. Melee tournament. They are ranked 1 − 20, and playern 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 ofpairs of players that win the same number of games.
解析

英文解析

  1. 20 players are playing in a Super Smash Bros. Melee tournament. They are ranked 1 − 20, and playern 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 ofpairs 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. Inorder for each player to play 18 games in the tournament, each must appear once in these 10 unplayedmatches. Players n and n + 1 will win the same number of games if, in the matching, they are matchedwith each other, or n plays a player a > n + 1 and n + 1 plays a player b < n. (Note no other pairs ofplayers can possibly win the same number of games.) The first happens with probability (as there 1
    ( n − 1)(20 − n − 1)19
    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 gamesis the sum of these probabilities. We compute
    ( )
    ( ) ( )
    19 18
    ∑ ∑19
    1 ( n − 1)(20 − n − 1) 1 n (18 − n ) + = + = 1 + = 4 .3
    19 323 19 323 323
    n =1 n =0