PROBLEM LINK
DIFFICULTY
SIMPLE
PREREQUISITES
Simple Math
PROBLEM
You are given 3 types of tickets.
- A tickets of type 1, the winning ticket
- B tickets of type 2, the losing ticket
- C tickets of type 3, the try again ticket
You take out D tickets from the sealed box containing all the tickets.
Now, you play the following game
- Take out a ticket from the box
- If the ticket is of type 1, you win. End the game.
- If the ticket is of type 2, you lose. End the game.
- If the ticket is of type 3, repeat the game from step 1.
QUICK EXPLANATION
The problem was originally posted with the constraint that
D ≤ A+B+C
This meant that the probability that only type 3 tickets remain was non-zero. MugurelIonut pointed out to the us, on the second day of the contest, that his accepted solution gives the wrong answer for cases where
D ≥ A+B
The judge cases indeed had the wrong answers for such cases. We will discuss in the end, what the answer for such cases is and what would the complete solution have been if the constraints weren’t changed and only the test cases were updated.
But, to maintain the difficulty level of the problem (relative to the problem set), we decided to change the constraint on D to
D < A+B
This ensures there is always either a winning, or a losing ticket after removing D tickets from the box.
EXPLANATION
Let us find the answer when D < A+B.
P(a,b,c,d) = probability that you win if you have a tickets of type 1, b tickets of type 2, c tickets of type 3 and you take out d tickets before starting the game. We know that
P(0,0,c,d) = 0, where c > 0 AND d ≤ c P(a,0,c,0) = 1, where a > 0 AND c ≥ 0 P(0,b,c,0) = 0, where b > 0 AND c ≥ 0 P(a,b,0,0) = a/(a+b), were a > 0 AND b > 0
Now, we will prove by induction, the following hypothesis
Given that either a > 0, or b > 0 P(a,b,c,0) = a / (a + b)
Firstly, we can see that the following holds true in our hypothesis
P(a,0,c,0) = a / a = 1, is satisfied for all a > 0 AND c ≥ 0 P(0,b,c,0) = 0 / b = 0, is satisfied for all b > 0 AND c ≥ 0
Because of our assumption, a > 0 OR b > 0, one of the base cases - P(0,0,c,0) - is no longer applicable, and we do not need to consider it. But the other base cases must be satisfied by our hypothesis
P(a,b,0,0) = a / (a+b), is satisfied for all a > 1 AND b > 1 AND c = 0
The above is of course true. The probability of winning is equal to the probability of picking the winning ticket - otherwise you instantly lose, since there are no try again tickets and you can only pick the losing ticket.
Now let us assume that the hypothesis is true for some c = t.
P(a,b,t,0) = a / (a+b)
Now, for c = t+1
P(a,b,t+1,0) = (a / (a + b + t+1)) // if type 1 ticket is selected + (t+1 / (a + b + t+1)) * P(a,b,t,0) // if type 3 ticket is selected P(a,b,t+1,0) = (a / (a+b+t+1)) + (t+1 / (a+b+t+1)) * (a / (a+b)) P(a,b,t+1,0) = (a / (a+b+t+1)) * (1 + (t+1 / a+b)) P(a,b,t+1,0) = (a / (a+b+t+1)) * ((a+b+t+1) / (a+b)) P(a,b,t+1,0) = a / (a+b)
Hence, if the hypothesis is true for c = t, it is also true for c = t+1.
Thus, for all c
Given a > 0 OR b > 0 P(a,b,c,0) = a / (a + b)
Now, We will prove using induction, that
Given d < a+b P(a,b,c,d) = a / (a + b)
First, we can easily see that out hypothesis is correct in the following cases
P(a,0,c,d) = a / a = 1 P(0,b,c,d) = 0 / b = 0
What we need to show that our hypothesis is correct in the base case d = 0.
P(a,b,c,0) = a / (a + b)
But the above is only true when a > 0 OR b > 0. We can see that since d < a+b, we will always end up with either a > 0 or b > 0.
Hence, the hypothesis is true in the base case. Now we move on and assume that the hypothesis is true for some d = t.
P(a,b,c,t) = a / (a + b)
We have to show that the hypothesis is also true for d = t+1.
P(a,b,c,t+1) = (a / (a+b+c)) * P(a-1,b,c,t) + (b / (a+b+c)) * P(a,b-1,c,t) + (c / (a+b+c)) * P(a,b,c-1,t) P(a,b,c,t+1) = (a / (a+b+c)) * ((a-1) / (a+b-1)) + (b / (a+b+c)) * (a / (a+b-1)) + (c / (a+b+c)) * (a / (a+b)) P(a,b,c,t+1) = (a / (a+b+c)) * ( (a-1) / (a+b-1) + b / (a+b-1) + c / (a+b) ) P(a,b,c,t+1) = (a / (a+b+c)) * ( (a+b-1) / (a+b-1) + c / (a+b) ) P(a,b,c,t+1) = (a / (a+b+c)) * ( 1 + c / (a+b) ) P(a,b,c,t+1) = (a / (a+b+c)) * ((a+b+c) / (a+b)) P(a,b,c,t+1) = a / (a+b)
Hence, the answer for the problem for all the inputs provided for this problem is a / (a+b).
Now, let us consider how to use this much information to solve the cases where D ≥ A+B. There are two possibilities we must consider after removal of D tickets
- X = There are no tickets of type 1 or type 2
- Y = There is at least 1 ticket of type 1 or type 2
We know that
X + Y = 1 total ways for selecting D tickets = ^{A+B+C}C_{D} ways for selecting tickets such that there are no tickets of type 1 or type 2 left = ^{C}C_{D-A-B} Hence, X = ^{C}C_{D-A-B} / ^{A+B+C}C_{D} Y = 1 - X
Now, we know the probability of winning if D < A+B is equal to A / (A+B).
We wish to know the probability of winning, given that there is at least one ticket of type 1, or type 2 left at the end of discarding D tickets. This conditional probability can be shown to be equalivalent to the case where D < A+B.
The sequence of discarding tickets doesn’t matter. It only matters, which tickets were discarded.
Since discarding each ticket is an independent event, we calculate the probability of discarding a sequence of tickets by multiplying the probabilities of the selections of the respective type of tickets.
For example, assume A = 10, B = 20, C = 30. Let us consider discarding (Type 1)(Type 2)(Type 1)(Type 3)
The probability would be = (10 / 60) * (20 / 59) * (9 / 58) * (30 / 57)
If we were to instead discard tickets in the order (Type 3)(Type 1)(Type 1)(Type 2)
The probability would be = (30 / 60) * (10 / 59) * (10 / 58) * (20 / 57)
Which is still the same.
This is important because, now given any sequence of discards, we can club all the discards of type 3 tickets to the beginning. Now, the necessary and sufficient condition for us to ensure at least one type 1 or type 2 ticket in the end is
Discard D-A-B+1 type 3 tickets
We can assume that these tickets were discarded in the beginning without affecting the probabiliy of the outcomes. Thus, the conditional probability of winning when there is at least 1 ticket of type 1 or type 2 is equal to the conditional probability of winning when at least D-A-B+1 tickets of type 3 have been discarded. This is equal to
P(A,B,A+B+C-D-1,A+B-1)
Which, by our solution to the problem for a D < A+B is already shown as A / (A+B). Now, we can apply Bayes Theorem and find the actual probability of winning
Y * A / (A+b) OR (1 - ^{C}C_{D-A-B} / ^{A+B+C}C_{D}) * A / (A + B)
Which completes our solution for any D.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.