Regarding - FUNPROB
The solution is :
int N, M;
while(1) {
scanf("%d %d", &N, &M);
if (0 == N && 0 == M) break;
if (N > M) printf("0.000000\n");
else {
double res = (double) (M-N+1) / (M+1);
printf("%.6f\n", res);
}
}
My question is regarding line
res = (M-N+1) / (M+1);
How to arrive at the conclusion that the probability is calculated in this way ?
At first it is obvious that if N>M
probability is zero.
now I want to use indication on N
to prove. consider M>0
I want to prove for every N=<M
we have res = (M-N+1) / (M+1)
for N=0
it is obvious that probability is 1
.
For N=1
put every body we 5$
in a queue in arbitrary order, now for the one person with 10$
you could put him every where except in front of the queue so you have between M+1
places that are available you have M+1-1
choices. so for N=1
you have : res = (M-1+1) / (M+1)
suppose formula is correct for every N=<k
I want to prove that if N=k+1
formula is still correct. for that put M
people with 5$
and k
people with 10$ in a arbitrary queue. we suppose that res = (M-K+1) / (M+1)
is the probability of working this queue and every body could have his ticket. consider one of the working queues in this queue if a 10$
person is behind 5$
person remove both of them and do this recursively until there is no 5$
person. this will work because as I said above the first person of the queue is a 10$
one, and also I said that N<M
the probability of putting the K+1
person in the queue is choosing one place among M-k+1
because we remove k
10$
person from the queue. and it is like what we said for N=1
so we have probability of putting K+1
th 5$
person in the queue is : ((M-k) - 1 +1) / ((M - k) +1)
(*) and by indication we have that probability of a working queue for N=k
is : (M-k +1) / (M +1)
( * ) from () and ( * *) we have probability of putting K+1
people with 10$
and M
people with 5$
in a queue with questions condition is :
[((M-k) - 1 +1) / ((M - k) +1)] * [(M-k +1) / (M +1)] = ((M-k) - 1 +1) / (M +1) = (M-(k+1) +1) / (M +1)
And it is end of the proof :).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With