Processing math: 100%

Problem #368

Skill Issue

In a knockout tournament with n = 2^k players, each player's skill is independently drawn from a uniform distribution on the interval [0, 1]. When two players with skills S 1 and S 2 compete, the "lead" of the game is given by | S 1 - S 2 |, and the player with the higher skill advances to the next round.

The organizers aim to minimize the total sum of the leads across all matches in the tournament.

For example, if there are 4 players with skills {0.3, 0.6, 0.4, 0.5}, an optimal pairing strategy might be to match players with skills 0.6 and 0.5 and players with skills 0.3 and 0.4, resulting in a total lead sum of (0.6 - 0.5) + (0.4 - 0.3) + (0.6 - 0.4) = 0.4.

Given k = 12345678987654321, find the expected sum of leads modulo 10^9 + 7.

Contributed by SANATAN SHARMA

Solved by 12 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.