PROBLEM LINK:Practice Setter: Abdullah Aslam DIFFICULTY:EasyMedium PREREQUISITES:Probability, Modular arithmetic and a bit of proof. (Setter says "Proof by intuition"). PROBLEM:There are initially $N$ indistinguishable boxes, exactly one of them containing one magic pill. You have to find the probability of finding the box containing the magic pill in at least one operation when you can perform operation $M$ times. In one operation, you can do either one of the following two.  Make a guess. If the chef finds the box, the game is over. Otherwise, $K$ more indistinguishable empty boxes are added every time a guess is made. Let's call it a guess operation.  Remove $i*K$ boxes such that $i \geq 0$ and $i*K \leq X$ where $X$ is the number of boxes present. No guess is made here. Let's call it a remove operation. Important to notice is that $N < K$. QUICK EXPLANATION
EXPLANATIONFirst thing, Let us consider it's the last move. It's obvious that making a guess now is better, than making a remove because making a guess increases your chances of winning. The final number of boxes is useless. Secondly, At any point during the game, Number of boxes is $X = N+x*K$ for some $x \geq 0$ When performing remove operation, we always choose to remove the maximum number of boxes we can (to maximize win probability), which happens to be $x*K$, leaving $N$ boxes behind. This also implies that if the number of boxes is $N$ before the current move, it makes sense to make a guess, since remove operation cannot remove any box at all. So, strategy maximizing win probability never have two consecutive remove operations. Remember $K > N$. Let's assume $K = N+d$. If we have $N$ boxes, it's obvious we make a guess. The number of boxes becomes $2*N+d$. Now comes the interesting part. Suppose we have more than one move remaining, with $2*N+d$ boxes before the current move, with the second move being a guess move. Now, what is better? The first move to be a guess move or to be a remove operation. Let's analyze both cases. In the first case, the Number of boxes before the second move is $N$, winning probability in these two moves is $1/N$. In the second case, Probability of win = P(win at first move)+P(win at second move)  P(win at both moves). The number of boxes before the second moves is $3*N+2*d$. So, the probability becomes $\frac{1}{2*N+d} + \frac{1}{3*N+2*d}  \frac{1}{(2*N+d)*(3*N+2*d)} = \frac{5*N+3*d1}{(2*N+d)*(3*N+2*d)}$. Lets multiply numerator by $N$, we have $\frac{5*N^2+3*d*NN}{6*N^2+7*d*n+2*d^2}$. It can be seen, that with $N,d \geq 1$, this probability is always less than 1. Dividing both sides with $N$, we have $\frac{5*N+3*d1}{6*N^2+7*d*N+2*d^2} < \frac{1}{N}$. Hence, we can see, that it is better to perform a remove operation and then make a guess, rather than making two consecutive guesses when we have $N+K$ boxes available. So, our final optimal strategy looks like. Make a guess. The number of boxes now is $N+K$. Perform remove and make another guess and so on. But as we noted earlier, the Last move shall always be guessing, which we shall ensure (There is two consecutive guess in the end when $M$ is even). Now, if $M$ is odd, we are making $(M+1)/2$ guess when at each guess we have $N$ boxes. It shall be complicated to handle inclusionexclusion here, and the simpler way is to calculate the probability of losing and takes its complement. The probability of losing is just the product of the probability of losing at each turn. Probability of losing is $\frac{(N1)^{(M+1)/2}}{N^{(M+1)/2}}$. So, probability of winning become $1\frac{(N1)^{(M+1)/2}}{N^{(M+1)/2}}$. When $M$ is even, we have $M/2$ guesses with $N$ boxes present, and one guess (last one) with $N+K$ boxes. Probability of winning here is $1\frac{(N+K1)*(N1)^{M/2}}{(N+K)*N^{M/2}}$. Implementation is left as an exercise. Time ComplexityTime complexity here is $O(log(M))$ per test case due to fast power. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Feb, 23:51

I couldn't think much for this problem, I don't know why, though I asked some of my friends (after the contest ended) how they solved it. Almost everyone noticed a pattern in the numerator part of the probability, but I couldn't. I figured out that the denominator will definitely be $N^{\lfloor\frac{(M + 1)}{2}\rfloor}$, but couldn't really find a direct formula for the numerator part, obviously because I was thinking way more than what was needed. But I did figure out what was the "Optimal Move" for this game, at a very early stage of my solution building, that helped me move in the right direction (still it took a lot of time to do it, so silly of me). So, I started seeing it differently. I found a recurrence relation for the numerator and built a Dynamic Programming solution for this problem (I knew it will fetch me only 40 points). The point I noticed for the formation of my recurrence was this: $\frac{A\times N + B  A}{B \times N}$, where $\frac{A}{B}$ was the winning probability just before this move Also, for the first Guess move, the probability would be $\frac{1}{N}$ $\therefore$ for every $i^{th}$ Guess move, the numerator can be expressed as a recurrence function $f(i)$ (which I figured out is) $f(i) = (N  1) \times f(i  1) + N^{(i  1)}$ And the denominator will be $N^{i}$ for every $i^{th}$ Guess move After solving this recurrence (using the characteristic equation method), I found out that $f(i) = N^{i}  (N  1)^i$ (when $N = 1$, winning probability is also $1$) And for the last move when $M$ is even, I used the formula, $\frac{A\times N + B  A}{B \times N}$ (as mentioned above). So I solved it directly with this formula, by literally calculating everything on paper and not observing it in front of a screen! answered 16 Feb, 20:20

proof of taking xoxox... if m%2==1 or xoxo.. if m%2==0 and not xxxx where x stands for operation of type 1 and o stands for operation of type 2 answered 18 Feb, 23:16

How do you handle the "tail probability" in the proof? If you take a guess you change the probability for all the following moves. If you just use induction, the math is harder because the Has anybody worked out the math? answered 19 Feb, 15:59
