Game Of Chance
Time limit3sMemory limit512 MB
For each m, find the limit of the expected score difference in a two-player optimal-stopping game where the choice holder assigns a random number to themselves or the opponent.
- Level
Medium7 of 10
- Topics
- Probability, Game theory, Math, Dynamic programming
- Solved
- No attempts yet
Problem
Billionaires Robin McBobin and Ronald Dump are playing the Game of Chance.
The game takes (n) turns. On each turn, one of the players has the right of choice, and Robin gets it for the first move. On each turn, an integer chosen uniformly and independently from (1) to (m) appears on the screen. The player with the right of choice has to choose whether to take this number and pass the right of choice to the opponent, or to give this number to the opponent but keep the right of choice.
Both Robin and Ronald are more interested in dominating their opponent than in gaining scores, so both choose the option that maximizes the expected difference between their sum of numbers and the opponent's. Both play optimally.
Let (d_n) be the expected value of the difference between Robin's sum and Ronald's sum after (n) turns. It can be proven that for (m \ge 3), there exists a rational number (d) such that (\lim_{n \to \infty}{d_n} = d). You have to find this number.
Input
The first line of input contains a single integer (t), the number of test cases ((1 \le t \le 5 \cdot 10^5)).
Each test case is given on a single line containing a single integer (m) ((3 \le m \le 10^9)).
Output
For each test case, if (d = \frac{P}{Q}) with (P) and (Q) coprime, output ((P \cdot Q^{−1})) mod ((10^9 + 7)). It is guaranteed that (Q \not\equiv 0) (mod (10^9 + 7)).
Hint
For (m = 3), the answer is (d = 1). For (m = 4), the answer is (d = 1.333\dots = \frac{4}{3}).