The Probability Of Winning

Refer:
http://www.codechef.com/problems/PROB

Proof:
assumption:p(t1,t2,t3)=t1/(t1+t2)
There are two parts to the proof .
1. Coins of type 3 don't matter .
2. Initial draw doesn't matter .

You can prove both the claims by mathematical induction
Proof 1 :
p(t1,t2,t3) = t1/(t1+t2+t3) + t3 / ( t1+t2+t3) * p(t1,t2,t3-1) . ( Statement 1 )
By induction hypothesis ,
p(t1,t2,t3-1) = t1/(t1+t2) .
which proves Statement 1 gives us assumed formula

Proof 2 :
p(t1,t2,t3,t4) = t1/(t1+t2+t3) * p(t1-1,t2,t3,t4-1) + t2/(t1+t2+t3) * p(t1,t2-1,t3,t4-1) + t3/(t1+t2+t3) * p(t1,t2,t3-1,t4-1) . (statement 2)
By induction hypothesis ,
p(t1-1,t2,t3,t4-1) = (t1-1)/(t1-1+t2)
p(t1,t2-1,t3,t4-1) = (t1)/(t1+t2-1)
p(t1,t2,t3-1,t4-1) = (t1)/(t1+t2)
which proves statement 2 gives us assumed formula.

alternative solution:
the logic is split in two parts:

1. t4 has no significance : Note that these tickets are removed randomly, so in some cases the prob of winning will increase and in others it will decrease. Overall, it will have no effect. I was satisfied with this intuition.
2. t3 has no significance : I actually worked this out mathematically. Let r denote the total number of tickets then we can get,
   P[win] = (t1/r)(1 + t3/(r-1) + t3 (t3-1)/((r-1)(r-2)) + ...
   P[loss] = (t2/r)(1 + t3/(r-1) + t3 (t3-1)/((r-1)(r-2)) + ...

Note that the big multiplicative term is same in both and can be replaced by L.
Also P[win] + P[loss] = 1
So, we have
P[win] + P[loss] = (t1/r + t2/r) * L
1 = (t1/r + t2/r) * L
L = r/(t1 + t2)
We can substitute this value of L back in P[win],
P[win] = (t1/r)* (r/(t1+t2))
P[win] = t1 / (t1+t2)

Program:
#include<stdio.h>
#include<math.h>

int main(){
    long long t,a,b,c,d;
 double ans;
 scanf("%lld",&t);
 while(t--){
  scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
  ans = a/(double)(a+b);
  ans = round(ans*10000000)/10000000;
  printf("%0.7f\n",ans);
 }
 return 0;
}