Hacker News Reader

Comment by dangoldin | Hacker News Reader

When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 (http://projecteuler.net/problem=267). It has a few "aha" moments but also requires coding to get it done.

View on HN

It surprises me that there's a unique 12 digit answer to this. If you bet proportion f of your income every round, then if you win n coin flips, shouldn't you have (1+2f)^n (1-f)^(1000-n) £? For a given f, it takes a certain number of heads for this value to exceed 1B£, but I'd expect a range of f values that all require the same minimal number of heads results to break 1B£. Unless there's a value of f that produces exactly 1B£ for the minimal needed number of heads (or the set of such f differ only after 12 digits). That seems unlikely...

EDIT: Just realized that the problem asks for the odds of being a billionaire, not f. So there are probably a good number of f that work, but they all produce the same odds.

As a finance person I really like this one. I'll have to check it out when I get home from work. Thanks!

Glad to help! If you run into any trouble let me know (email in profile) and I'll provide some hints.

Hey, thanks. This was a fun problem. I got a little bit obsessed though, and I wonder if it might be possible to finish the problem on pencil and paper. I am sure I can finish an approximate version, but I am not sure I can get 12 digits. Did you try something like this?

P.S. I must apologize for abstractly referring to a solution approach as "this", but I didn't want to create a spoiler in case anyone else had felt inspired.

I wasn't able to do it with pen and paper and suspect it's not possible. The 1000 flips and the 1 billion is arbitrary so it seems you'd always have to work with real numbers. I may be completely wrong though.

This thread is about solving them using pen and paper:

http://forum.projecteuler.net/viewtopic.php?f=50&t=1982

I don't see this problem listed, but I didn't look through the whole thread.

I actually don't know how to solve it programmatically without doing things that feel nasty.

Solved it with pencil and paper, if "pencil and paper" includes asking Wolfram Alpha a few questions :)

Hey, who did you interview and for what position? And how many of these people succeeded? I've solved about 50 project Euler problems, but only 1 or 2 with number above 200. I'm not a genius, didn't study maths, but it's imho quite hard to solve any Euler problem at an interview, even if you're a decent thinker. Ok, there are few easy ones, but none of these with 3 digit numbers.

It was for quantitative engineer roles at Yodle (adtech startup). The goal wasn't really to get to a solution since it's not possible without sitting down to code but more to get them thinking about it and how they'd structure the problem. I don't remember offhand how many people got it but the ones with a statistics/data background ended up having the right approach and the ones that didn't got it with a few hints.

Is there a list with Project Euler problems that focus less on number theory like this one?

A lot of Project Euler is very "mathy", requiring you to read up on some mathematical shortcuts - I think https://www.hackerrank.com/ is a bit more CS-focused, i.e., there's always a specific data-structure or algorithm that solves the problem.

You might like Rosalind (http://rosalind.info/). It's like Project Euler, but with a strong bioinformatics (espeically) genetics slant. There is certainly math, especially combinatrics (for obvious reasons), but much more so that Euler there is background given in the problems, so it's often much more about coding a reasonable implementation than about knowing some obscure corner of number theory.

I like Programming Praxis (http://programmingpraxis.com/), it has mostly algorithmic problems and the questions also include solutions.

I really enjoy the types of problems on PuzzleNode[1]. My local coder meetup does one each month for code reviews. Their puzzles are just deep enough to where you need to think through how you'll design the system. They're really fun for exploring different programming techniques.

[1]http://www.puzzlenode.com/

My solution would be:

For one coint toss, I get:

(previous winnings) x (1+f) if I win

(previous winnings) x (1-f) if I lose

Thus, w being the number of times I win, I get the total $$ we would have:

(1+f)^w x (1-f)^(1000-w)

But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4):

(1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500)

So, now we can take an f, calculate the number of w's that put us above 1B$, and sum up the ponderation for each case. Then find the right f that optimized the chance of being a billionaire. This chance is the solution.

It's actually 1+2f versus 1-f. (I agree that the wording is not very clear. I misinterpreted it too at first and was very confused at how my solution was being rejected. If you look at the short worked example they give, though, it's unambiguous.)

You're using the normal approximation to the binomial distribution. It may or may not be a good enough approximation. Better to do the binomial thing exactly. This requires arbitrary-precision integer arithmetic, but that's pretty easily available.

I get 1/4 as the optimal value for f. Given a 500/500 win lose, then final money = (1-f)^500*(1+2f)^500 = (-2f^2+f+1)^500. To find the maximum, the ^500 is irrelevant. Differentiating and finding a gradient of 0 gives: -4f+1=0 or f=1/4. Just by checking values, it seems I need to lose more than 555 times before I finish with less then 1 billion. I'm not sure how to calculate the probability of that, your formula doesn't seem to work. In any case, the problem seems to be purely mathematical rather than requiring code to be written.

I have a different f that can win with only 433 heads.

Did you use the Kelly Criterion or did you do something else?

I used something else - don't want to give too much away but the general idea is to try it on a smaller problem (4 flips, $5, etc) and seeing if any patterns develop.

The Kelly criterion doesn't quite apply in this problem, since you are asked to optimize a more conservative strategy, namely to guarantee (with high probability) a certain amount of winnings rather than maximize log(winnings). In fact the Kelly value for f (in the problem's notation) is 0.25.

Nice problem, made me come back to projecteuler! I hadn't solved anything for 3 years.

Is there any danger that someone has seen the problem?

Yea - then we just walk through their answer to make sure they get the reason it works and ways to improve it. It's usually quicker and leaves time for another question that they hopefully haven't heard.

Reply on news.ycombinator.com