A bottle of drug with n tablets. Every time eat a half of tablet and put another half back to bottle if you get a full size tablet. Eat the half tablet if you get a half size tablet.
Calculate the odd of taking a full size tablet at the kth taking.
The only thing which comes in my mind is that this problem could be solved by Markov chain evolving for k steps.
This problem looks quite interesting. Basically you need to keep track of the number of full tablets and half tablets in the bottle at step k. If you know that number, the probability is trivial: P(full) = full_tablets / (full_tablets + half_tablets).
Let's start with a simple example. n = 3.
- At the beginning we have 3 full tablets in the bottle: FFF
- 1st step: FFH
- 2nd step: FHH or FF
- 3rd step: HHH or FH
- 4th step: HH
- 5th step: H
- 6th step: empty bottle
but not all the configurations have the same probability. In step 3, HHH only happens 1 out of 3 cases.
So basically we need to count how many times each case appears. There are only two ways to reach a given configuration, extracting a full table or a half table. So, reaching any combination is the sum of reaching those two other combinations together. This creates an interesting triangle, similar to the Pascal triangle
k=2, 1 1
k=3, 1 2
k=4, 1 3 2
k=5, 1 4 5
k=6, 1 5 9 5
k=7, 1 6 14 14
k=8, 1 7 20 28 14
in each row you have the numbers of ways to extract A full tables and B half tables, A from k to k/2 and B=A-k. For k=8 you have:
- 1 way to extract 8 full tablets
- 7 ways to extract 7 full tablets and 1 half table
- 20 ways to extract 6 full tablets and 2 half tables
Remember that A >= B and A+B = k.
One caveat. If k>n then there are some combinations that do not have more full tables. You need to start adding zeroes to the triangle from left to right.
Putting all this together you have:
- A, number of full tables extracted so far
- B, number of half tables extracted so far
- full tablets remaining: n - A
- total tablets in the bottle: n - B
- probability of extracting exactly A full tables and B half tables up to step k: T(K, i) / sum(T(K, *))
With that information it should be trivial to write a program to compute the probability of extracting a full tablet at step k.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.