Euler Projesi 267. Soru

Milyarder

Size eşsiz bir yatırım fırsatı veriliyor.

1 £ sermaye ile başlayarak bir hilesiz para atma olayında 1000 atış için her seferinde sermayenizin sabit bir f oranını seçip bahse girebilirsiniz.

Tura için bahsinizin iki katı kadar kazanırken yazı için bahisiniz kadarını kaybedersiniz.

Örneğin eğer f = 1/4 ise ilk atış için bahsiniz 0,25 £ olurken, eğer tura gelirse 0,5 £ kazanırsınız ve 1,5 £ paranız olur. Daha sonra bahsiniz 0,375 £ olurken eğer ikinci atış yazı ise 1,125 £ paranız kalır.

1000 atıştan sonra en az 1.000.000.000 £ kazanma şansınızı en üst düzeye çıkaracak şekilde f seçimi yaparsanız milyarder olma şansınız nedir?

Tüm hesaplamaların tam olduğu (yuvarlama olmadığı) kabul edilir, ancak cevabınızı 0,abcdefghijkl biçiminde 12 ondalık basamağa yuvarlayarak veriniz.

Cevap: 0,999992836187

Python: import math def bisect_left(f, n): lo, hi = 0, n while lo < hi: mid = (lo+hi)//2 print(mid, f(mid)) if f(mid) < 0: lo = mid+1 else: hi = mid return lo niter = 1000 total = 10 ** 9 def succ(f): def t(n): return (1 + 2 * f) ** n * (1 - f) ** (niter - n) return t def c(n, m): return math.factorial(n) // math.factorial(m) // math.factorial(n - m) def mx(f): x = bisect_left(lambda x: succ(f)(x) - total, niter + 1) print(x, succ(f)(x)) return sum(c(niter, k) for k in range(x, niter + 1)) / 2 ** niter print(mx(0.148)) Ocaml: let rawr f = let a,b = log (1.+.2.*.f), log (1.-.f) in (9.*.log 10. -. 1000.*.b)/.(a-.b) let wins = let rec g (a,ra) (b,rb) (c,rc) = if (c-.a)<0.000000001 then rb else let d = (a+.b)/.2. and e = (b+.c)/.2. in let rd = rawr d and re = rawr e in if re <= rb then g (b,rb) (e,re) (c,rc) else g (a,ra) (d,rd) (b,rb) in 1+int_of_float (g (0.1, rawr 0.1) (0.5, rawr 0.5) (0.9, rawr 0.9)) let maketab n = let a = Array.make (n+1) 0. in a.(0) <- 1.; for i=1 to n do for j=n downto 1 do a.(j)<-(a.(j)+.a.(j-1))/.2. done; a.(0)<-a.(0)/.2. done; a let answer = let t = ref 0. and a = maketab 1000 in for i=1000 downto wins do t:= !t+.a.(i) done; !t gp: q(f)=sum(x=0,1000,if(r=(1+2*f)^x*(1-f)^(1000-x)>1000000000,binomial(1000,x),0))/2^1000 forstep(i=0,0.2,0.01,print(i," ",1.*q(i))) Mathematica: f[x_] := (9*Log[10] - 1000*Log[1 - x])/Log[(1 + 2*x)/(1 - x)]; g[x_] := f'[x]; r = FindRoot[g[x] == 0, {x, 0.0001}] {x -> 0.146883922441} fmin = r[[1]][[2]] 0.146883922441 minw = Ceiling[f[fmin]] 432 Print["Solution: ", N[Sum[Binomial[1000, k]/2^1000, {k, minw, 1000}]]] Solution: 0.999992836187 C/C++: #include <stdlib.h> #include <stdio.h> #include <math.h> #include <memory.h> #include <string.h> #include <time.h> typedef __int64 int64; typedef unsigned __int64 uint64; struct timer { clock_t t; timer() { t = clock(); } ~timer() { printf("runtime %.3f secs\n", getTime()); } double getTime() { return ((double)clock()-(double)t)/(double)CLOCKS_PER_SEC; } }; double choose(int n, int k) { double accum = 1; int i=0; while (++i<=k) accum *= (double)(n-k+i) / i; return accum; } void f267() { // for a=number of heads -> F(a,f)=(1+2f)^a * (1-f)^(1000-a) // dF/df=0 -> f_max(a)=(3a-1000)/2000 // find the lowest a that satisfies // F(a,f_max(a))=(3a/1000)^a * ((3000-3a)/2000)^(1000-a) > 10^9 double lg2000=log10(2000); int a=500, b=0, diff; while (diff=a-b, b=a, diff!=0) { if (diff<0) diff=-diff; double a3=a*3, d=a*(log10(a3)-3)+(1000-a)*(log10(3000-a3)-lg2000); if (d>9) a-=diff/2; else a+=diff/2; } // find the number of ways to choose below this lowest a double t=0; while (--a>0) t+=choose(1000,a); printf("p=%.12f\n", 1-t/pow(2,1000)); } int main(int argc, char**argv) { timer t; f267(); return 0; } /* p=0.999992836187 runtime 0.002 secs */ Go: def sum_of_binomial(r): total = 1001 x = 1000 for i in range(1, r): x = (x * (1000 -i) // (i + 1)) print(x) total += x return total def n(f): return ceil((9 - 1000*log10(1-f)) / log10((1+2*f)/(1-f))) def search(): min = 1000 for i in range(1, 100000): b = n(i/100000) if b < min: min = b return min def main(): n = search() return (1 - (sum_of_binomial(n - 1) / 2**1000)) print(main())