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.