Imagine you have a bag, which is filled with N balls. Each ball can have the color black or white. You know that W balls in the bag are white.
If you extract a ball from the bag, the probability changes of the remaining balls.
Your job is it to output the ratio of the odds that you extracted kwhite balls after extracting s balls from the bag.
Balls are never put back into the bag!
Example:
You have 3 balls in the bag, 2 of which are white.
What is the probability of having 2 white balls by extracting 2 balls?
When A is the event of getting 2 white balls:
P(A) = Probability of getting 2 white balls = 2/3 * 1/2 = 1/3
P(!A) = Probability of not getting 2 white balls = 1-1/3 = 2/3
So the ratio P(A) : P(!A) is 1:2 (read 1 to 2).
The ratio 2:4 would be the same ratio, but both numbers are divisible by 2, so you need to reduce the ratio.
If you extract a ball from the bag, the probability changes of the remaining balls.
Your job is it to output the ratio of the odds that you extracted kwhite balls after extracting s balls from the bag.
Balls are never put back into the bag!
Example:
You have 3 balls in the bag, 2 of which are white.
What is the probability of having 2 white balls by extracting 2 balls?
2/3 * 1/2 = 1/3 When A is the event of getting 2 white balls:
P(A) = Probability of getting 2 white balls = 2/3 * 1/2 = 1/3
P(!A) = Probability of not getting 2 white balls = 1-1/3 = 2/3
So the ratio P(A) : P(!A) is 1:2 (read 1 to 2).
The ratio 2:4 would be the same ratio, but both numbers are divisible by 2, so you need to reduce the ratio.
Input
Line 1: An Integer N for the number of balls in your bag.
Line 2: An Integer W for the number of white balls in your bag.
Line 3: An Integer s for the size of your sample.
Line 4: An Integer k for the desired number of white balls in your sample.
Line 2: An Integer W for the number of white balls in your bag.
Line 3: An Integer s for the size of your sample.
Line 4: An Integer k for the desired number of white balls in your sample.
Output
Line 1:A : B, the odds ratio (in lowest terms) that k white balls are in your sample of s balls
Constraints
0 ≤ N ≤ 60
0 ≤ W ≤ N
0 ≤ s ≤ N
0 ≤ k ≤ s
0 ≤ k ≤ W
0 ≤ W ≤ N
0 ≤ s ≤ N
0 ≤ k ≤ s
0 ≤ k ≤ W
Solution
We calculate the Laplace-Probability by first determining the underlying set of \(s\) balls out of \(n\) balls without repetition, which are \({n\choose s}\). We then treat the draw of black and white balls separately. We first draw \(k\) white balls, which gives \(w\choose k\) possibilities and \(s-k\) black balls, which gives \(n-w\choose s-k\) possibilities and therefore
\[ P(X) = \frac{{w\choose k}\cdot{n-w\choose s-k}}{n\choose s} \]
When we take the probability as a rational number \(q=P(X)\), the odds are \(\frac{q}{1-q}\). Implemented in Ruby, the whole solution then looks as
n = gets.to_i
w = gets.to_i
s = gets.to_i
k = gets.to_i
def binom(n, k)
n = n - k
c = 1
for i in 1..k do
c = c * (n + i) / i
end
return c
end
q = Rational(binom(w, k) * binom(n - w, s - k), binom(n, s))
if 1 == q then
puts "1:0"
else
puts (q / (1 - q)).to_s.sub("/", ":")
end