Billionaire
You have 1 and want to become a billionaire (10^9). You flip a biased coin repeatedly (probability 1/2 heads, 1/2 tails). Before each flip, you choose a fixed fraction f (0 < f < 1) of your current...
Problem Statement
This archive keeps the full statement, math, and original media on the page.
You are given a unique investment opportunity.
Starting with £1 of capital, you can choose a fixed proportion, <var>f</var>, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.
Your return is double your bet for heads and you lose your bet for tails.
For example, if \(f = 1/4\), for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125.
Choosing \(f\) to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?
All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl.
Problem 267: Billionaire
Mathematical Analysis
Wealth After n Flips
After n coin flips with k heads and (n - k) tails:
W(n, k) = (1 + 2f)^k * (1 - f)^(n - k)
We become a billionaire if W(n, k) >= 10^9, i.e.:
k * ln(1 + 2f) + (n - k) * ln(1 - f) >= 9 * ln(10)
Minimum Heads Needed
For fixed f and n flips, the minimum number of heads k needed satisfies:
k >= [9 * ln(10) - n * ln(1 - f)] / [ln(1 + 2f) - ln(1 - f)]
Let g(f) = ln(1 - f) / [ln(1 + 2f) - ln(1 - f)] (note this is negative).
The minimum heads k_min(n, f) = ceil([9*ln(10) + n * |ln(1-f)|] / [ln(1+2f) + |ln(1-f)|])
Simplifying: k_min(n, f) = ceil(n * r(f) + c(f)) where:
- r(f) = -ln(1-f) / [ln(1+2f) - ln(1-f)]
- c(f) = 9*ln(10) / [ln(1+2f) - ln(1-f)]
Probability Calculation
The probability of becoming a billionaire in exactly n flips with fraction f:
P(n, f) = sum_{k=k_min}^{n} C(n, k) * (1/2)^n
As n -> infinity, by the law of large numbers, the fraction of heads approaches 1/2. So we need r(f) < 1/2 for the probability to approach 1.
The probability of having at least k_min heads out of n flips is:
P = sum_{k=k_min}^{n} C(n, k) / 2^n
We want to maximize this over f for each n, then take n -> infinity (in practice, large enough n).
Optimization
For large n, k_min(n, f) ~ n * r(f) + c(f). The probability is essentially:
P = 1 - Phi((k_min - n/2) / sqrt(n/4)) (by CLT approximation)
This is maximized when k_min is minimized. For large n, minimizing k_min/n means minimizing r(f). Taking the derivative of r(f) and setting to 0 is complex, so we optimize numerically.
Actually, for a fixed n, we compute k_min(f) = ceil(9*ln(10)/ln((1+2f)/(1-f))), and then the probability is sum_{k>=k_min}^n C(n,k)/2^n. We optimize over f for each n, and increase n until convergence.
Result
The maximum probability is 0.999992836187.
Correctness
Theorem. The method described above computes exactly the quantity requested in the problem statement.
Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer.
Complexity
- For each candidate n, binary search over f or grid search: O(n) for binomial sum
- Total: O(n * search_iterations)
Answer
Code
Each problem page includes the exact C++ and Python source files from the local archive.
#include <bits/stdc++.h>
using namespace std;
int main() {
// PE 267: You toss a biased coin 1000 times.
// Each toss: heads with prob 1/2, tails with prob 1/2.
// Before EACH toss, you bet a fixed fraction f of current wealth.
// If heads: gain 2*f*wealth (so wealth *= (1+2f))
// If tails: lose f*wealth (so wealth *= (1-f))
// Start with $1. Find max probability (over f) of ending with >= $10^9.
//
// n = 1000 flips. After k heads: wealth = (1+2f)^k * (1-f)^(1000-k)
// Need (1+2f)^k * (1-f)^(1000-k) >= 10^9
// k*ln(1+2f) + (1000-k)*ln(1-f) >= 9*ln(10)
// k >= [9*ln(10) - 1000*ln(1-f)] / [ln(1+2f) - ln(1-f)]
//
// For each f, k_min(f) = ceil([9*ln(10) - 1000*ln(1-f)] / [ln(1+2f) - ln(1-f)])
// Probability = P(Bin(1000, 0.5) >= k_min(f))
// Maximize over f.
//
// k_min is a step function of f. We want the smallest possible k_min.
// The continuous function g(f) = [9*ln(10) - 1000*ln(1-f)] / [ln(1+2f) - ln(1-f)]
// Minimize g(f) over f in (0, 1), then k_min = ceil(min g(f)).
int n = 1000;
double target = 9.0 * log(10.0);
// Find the f that minimizes g(f)
// g(f) = (target - n*ln(1-f)) / (ln(1+2f) - ln(1-f))
// = (target + n*|ln(1-f)|) / (ln(1+2f) + |ln(1-f)|)
// As f -> 0: g(f) -> target / (2f + f) ~ target/(3f) -> infinity
// As f -> 1: g(f) -> (target + inf) / (ln3 + inf) -> n = 1000
// So there's a minimum somewhere in (0,1).
// Use golden section search or ternary search
double lo = 1e-10, hi = 1.0 - 1e-10;
for (int iter = 0; iter < 200; iter++) {
double m1 = lo + (hi - lo) / 3;
double m2 = hi - (hi - lo) / 3;
auto g = [&](double f) {
return (target - n * log(1.0 - f)) / (log(1.0 + 2.0 * f) - log(1.0 - f));
};
if (g(m1) < g(m2)) {
hi = m2;
} else {
lo = m1;
}
}
double f_opt = (lo + hi) / 2;
auto g_func = [&](double f) {
return (target - n * log(1.0 - f)) / (log(1.0 + 2.0 * f) - log(1.0 - f));
};
double g_min = g_func(f_opt);
int kmin = (int)ceil(g_min - 1e-9);
// Check kmin and kmin+1 to be safe (ceiling might be off)
// For each candidate kmin, compute probability and take the best
long double best_prob = 0;
for (int km = max(0, kmin - 1); km <= min(n, kmin + 1); km++) {
// Check if there exists f such that wealth >= 10^9 with km heads
// (1+2f)^km * (1-f)^(n-km) >= 10^9
// At optimal f = (3*km - n)/(2*n):
if (3 * km <= n) continue; // f <= 0
double fstar = (3.0 * km - n) / (2.0 * n);
if (fstar <= 0 || fstar >= 1) continue;
double log_wealth = km * log(1.0 + 2.0 * fstar) + (n - km) * log(1.0 - fstar);
if (log_wealth < target - 1e-9) continue; // can't reach 10^9 with km heads
// Compute P(Bin(n, 0.5) >= km)
long double prob = 0;
for (int k = km; k <= n; k++) {
long double lt = lgammal(n + 1) - lgammal(k + 1) - lgammal(n - k + 1)
- (long double)n * logl(2.0L);
prob += expl(lt);
}
if (prob > best_prob) best_prob = prob;
}
printf("%.12Lf\n", best_prob);
return 0;
}
"""
Problem 267: Billionaire
Toss a fair coin 1000 times. Before each toss, bet a fixed fraction f of
current wealth. Heads: gain 2f*wealth (multiply by 1+2f). Tails: lose
f*wealth (multiply by 1-f).
Find the maximum probability of reaching $10^9 starting from $1.
Approach:
- After k heads out of 1000: wealth = (1+2f)^k * (1-f)^(1000-k)
- For fixed k, optimal f = (3k - 1000) / 2000
- Find minimum k where max wealth >= 10^9
- Probability = P(Binomial(1000, 0.5) >= k_min)
"""
from math import log, lgamma, exp, ceil
from decimal import Decimal, getcontext
def solve():
n = 1000
target = 9 * log(10)
# Find minimum k such that at optimal f, wealth >= 10^9
kmin = None
for k in range(n // 3 + 1, n + 1):
f_opt = (3 * k - n) / (2 * n)
if f_opt <= 0 or f_opt >= 1:
continue
log_wealth = k * log(1 + 2 * f_opt) + (n - k) * log(1 - f_opt)
if log_wealth >= target - 1e-12:
kmin = k
break
if kmin is None:
print("0.000000000000")
return
# Use Decimal for high-precision computation
getcontext().prec = 50
prob = Decimal(0)
two = Decimal(2)
two_n = two ** n # 2^1000
# Compute sum_{k=kmin}^{n} C(n,k) / 2^n using exact integer arithmetic
from math import comb
total = sum(comb(n, k) for k in range(kmin, n + 1))
prob = Decimal(total) / Decimal(two_n)
# Format to 12 decimal places
print(f"{prob:.12f}")
solve()