Problem
Author: Rishav Pati
Tester: Rajat De
Editorialist: Rishav Pati
DIFFICULTY:
EASY
QUICK EXPLANATION:
Direct application of gambler’s ruin. I was unaware of the topic while setting the question. Can be also solved by writing equations for all states in the game and finding pattern.
EXPLANATION
Let P_0,P_1, … P_{n+m} be the expected no. of turns if the 1st plater has 0,1 … n+m coins.
Clearly,
P_0 = P_{n+m}, P_1 = P_{n+m-1} and so on.
Now we know that P_0 = P_{n+m} = 0.
For 1 <= i < n+m, we can write,
P_i = (P_{i-1} + P_{i+1})/2.
Using this and the fact that P_{i} = P_{n+m-i},
We can easily obtain every P_i by substitution.
It can be observed that P_i = i*(n+m-i).