H. Game Of Chance

Codeforces

IDCF10212H

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

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, 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 for themselves. Both Robin and Ronald are more interested in dominating their opponent than in gaining scores, so both will choose the option which would maximize the expected difference between their and the opponent's sum of numbers. Both players play optimally. Let $d_n$ be the expected value of difference between Robin's sum and Ronald's sum after $n$ turns. It may be proven that for $m >= 3$, there exists a rational number $d$ such that $lim limits_{n arrow.r infinity} d_n = d$. You have to find this number. The first line of input contains a single integer $t$ which is the number of test cases ($1 <= t <= 5 dot.op 10^5$). Each test case is given on a single line containing a single integer $m$ ($3 <= m <= 10^9$). For each test case, if $d = frac(P, Q)$ such that $P$ and $Q$ are coprime, output $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$. For $m = 3$, the answer is $d = 1$. For $m = 4$, the answer is $d = 1. 333... = frac(4, 3)$. ## Input The first line of input contains a single integer $t$ which is the number of test cases ($1 <= t <= 5 dot.op 10^5$).Each test case is given on a single line containing a single integer $m$ ($3 <= m <= 10^9$). ## Output For each test case, if $d = frac(P, Q)$ such that $P$ and $Q$ are coprime, output $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$. [samples] ## Note For $m = 3$, the answer is $d = 1$. For $m = 4$, the answer is $d = 1. 333... = frac(4, 3)$.

Let $ m \in \mathbb{Z} $, $ m \geq 3 $. Let $ d $ be the limit of the expected difference $ d_n = \mathbb{E}[\text{Robin's sum} - \text{Ronald's sum}] $ as $ n \to \infty $, under optimal play. The value $ d $ satisfies the functional equation derived from the optimal stopping rule: $$ d = \frac{1}{m} \sum_{k=1}^{m} \max\left(k - d,\ -k + d\right) $$ This simplifies to: $$ d = \frac{1}{m} \sum_{k=1}^{m} |k - d| $$ Let $ t = \lfloor d \rfloor $, and define $ r = d - t \in [0,1) $. Split the sum at the point where $ k \leq d $ and $ k > d $: $$ d = \frac{1}{m} \left( \sum_{k=1}^{\lfloor d \rfloor} (d - k) + \sum_{k=\lfloor d \rfloor + 1}^{m} (k - d) \right) $$ Let $ t = \lfloor d \rfloor $, then: $$ d = \frac{1}{m} \left( t d - \frac{t(t+1)}{2} + \frac{m(m+1)}{2} - \frac{t(t+1)}{2} - (m - t)d \right) $$ Simplify: $$ d = \frac{1}{m} \left( (2t - m)d + \frac{m(m+1) - 2t(t+1)}{2} \right) $$ Multiply both sides by $ m $: $$ m d = (2t - m)d + \frac{m(m+1) - 2t(t+1)}{2} $$ Bring terms with $ d $ to left: $$ m d - (2t - m)d = \frac{m(m+1) - 2t(t+1)}{2} $$ $$ (2m - 2t)d = \frac{m(m+1) - 2t(t+1)}{2} $$ $$ d = \frac{m(m+1) - 2t(t+1)}{2(2m - 2t)} = \frac{m(m+1) - 2t(t+1)}{4(m - t)} $$ But $ t = \lfloor d \rfloor $, and for $ m \geq 3 $, it is known that $ d \in (1, 2) $, so $ t = 1 $. Thus, substitute $ t = 1 $: $$ d = \frac{m(m+1) - 2(1)(2)}{4(m - 1)} = \frac{m(m+1) - 4}{4(m - 1)} $$ Simplify numerator: $$ m(m+1) - 4 = m^2 + m - 4 $$ So: $$ d = \frac{m^2 + m - 4}{4(m - 1)} $$ This is the closed-form expression for $ d $. **Final Answer:** $$ d = \frac{m^2 + m - 4}{4(m - 1)} $$

API Response (JSON)

{
  "problem": {
    "name": "H. Game Of Chance",
    "description": {
      "content": "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, Robin gets it for the first move. On eac",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10212H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Billionaires Robin McBobin and Ronald Dump are playing the Game of Chance.\n\nThe game takes $n$ turns. On each turn, one of the players has the right of choice, Robin gets it for the first move. On eac...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ m \\in \\mathbb{Z} $, $ m \\geq 3 $.  \nLet $ d $ be the limit of the expected difference $ d_n = \\mathbb{E}[\\text{Robin's sum} - \\text{Ronald's sum}] $ as $ n \\to \\infty $, under optimal play.\n\nThe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments