<< problem 266 - Pseudo Square Root | A Modified Collatz sequence - problem 277 >> |

# Problem 267: Billionaire

(see projecteuler.net/problem=267)

You are given a unique investment opportunity.

Starting with £1 of capital, you can choose a fixed proportion, f, 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.

# My Algorithm

My function `getMinHeads`

performs a simple linear search for the minimum number of heads required to become a billionaire.

`ratio`

(which is f in the problem description) is slowly increased from 0 to 1 with a `step = 0.0001`

(works with larger values, such as `0.01`

, too).

The expected amount of money is (1 + 2f)^{heads} * (1 - f)^{tails}.

After 1000 tosses, this is equivalent to (1 + 2f)^{heads} * (1 - f)^{1000 - heads}.

The inner-most `for`

-loop tries to find the lowest value of heads where (1 + 2f)^{heads} * (1 - f)^{1000 - heads} >= 10^9.

My function `probability`

is simple Dynamic Programming code that returns the probability of at least `minHeads`

times observing a head after `maxTosses`

fair coin tosses.

## Alternative Approaches

There are mathematical ways to figure out the results of `getMinHeads`

with pen and paper but I like the simple and obvious code of my solution.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
// find minimum number of heads to become a billionaire

unsigned int getMinHeads(unsigned int tosses, double billion, double step = 0.0001)
{
unsigned int result = tosses;
// simple linear search
for (double ratio = 0; ratio < 1; ratio += step)
{
// won: gain twice the invested money
auto won = 1 + 2 * ratio;
// lost: invested money is lost
auto lost = 1 - ratio;
// try to have a billion with less heads than the total best
unsigned int heads = result;
for (; heads > 0; heads--)
{
// total amount of money
auto total = pow(won, heads) * pow(lost, tosses - heads);
// below one billion ? one step too far
if (total < billion)
{
heads++;
break;
}
}
// better than before ?
if (result > heads)
result = heads;
}
return result;
}
// return probability of tossing at least "minHeads" times head with a fair coin
// note: parameters "tosses" and "heads" are using during recursion only

double probability(unsigned int minHeads, unsigned int maxTosses, unsigned int tosses = 0, unsigned int heads = 0)
{
// enough heads ?
if (heads >= minHeads)
return 1;
// too few heads: can't achieve minHeads even if a series of heads only appears ?
if (maxTosses - tosses < minHeads - heads)
return 0;
// memoize
const double Unknown = -1;
static std::vector<double> cache(minHeads*maxTosses, Unknown);
auto id = heads * maxTosses + tosses;
if (cache[id] != Unknown)
return cache[id];
// fifty-fifty ...
auto result = 0.5 * probability(minHeads, maxTosses, tosses + 1, heads + 1) +
0.5 * probability(minHeads, maxTosses, tosses + 1, heads );
cache[id] = result;
return result;
}
int main()
{
// I wanna be a billionaire after 1000 coin tosses !
unsigned int tosses = 1000;
double money = 1000000000;
std::cin >> tosses >> money;
// determine minimum number of heads
auto minHeads = getMinHeads(tosses, money);
// compute probability for that number of heads (or more) after 1000 coin tosses
std::cout << std::fixed << std::setprecision(12)
<< probability(minHeads, tosses) << std::endl;
return 0;
}

This solution contains 13 empty lines, 17 comments and 4 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "100 1000000" | ./267`

Output:

*Note:* the original problem's input `1000 1000000000`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in less than 0.01 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

Peak memory usage was about 6 MByte.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

July 11, 2017 submitted solution

July 11, 2017 added comments

# Difficulty

Project Euler ranks this problem at **50%** (out of 100%).

# Links

projecteuler.net/thread=267 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

C#: www.mathblog.dk/project-euler-267-billionaire/ (written by Kristian Edlund)

Those links are just an unordered selection of source code I found using Google/Bing/Startpage/whatever.

You will probably stumple upon better solutions when searching on your own.

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 266 - Pseudo Square Root | A Modified Collatz sequence - problem 277 >> |