Actual interview brainteaser at a top flight shop

dtrader98 · Dec 23, 2009

Quote from Kovacs:

Come up with a three heads scenario where you don't think it'll win. I'll give you the betting sequence.

The point is (if I'm interpreting properly) you must have a rule set that wins in ALL possible cases of three heads
and has a net +100 gain by the end of the third head.

It is a simple matter to come up with those
cases. The difficulty lies in coming up with
the strategy that guarantees the above.

nitro · Dec 23, 2009

Quote from Pension_Admin:

I think this is correct. Could someone else double check to confirm?

Where is the rule for the amount to bet at each turn?

KarateChop · Dec 23, 2009

Quote from nitro:

Where is the rule for the amount to bet at each turn?

The strategy is posted in the thread. SjFan, the strategy I posted will guarantee you win $100 if three heads appear in 5 flips. Are you saying there is a unique solution? One that does not require you to alter your final 3 bets depending on the outcome of the first 2 tosses?

nitro · Dec 23, 2009

Quote from KarateChop:

The strategy is posted in the thread...

Seems to work.

I am more interested in understanding why $37.50 works and then $25 $50 $75. Does any other starting bet work with the right tripplet of betting after that? What if the starting number is $160 and you have to get to $320? What is the general equation for the first number, and then for the resulting bets? What if there were n trials instead of 5?

Was $37.50 just a lucky guess?

KarateChop · Dec 23, 2009

Quote from nitro:

Seems to work.

Was $37.50 just a lucky guess?

No, it was not a lucky guess. I started with the fact that if you lost the first 2 tosses, you still needed to be able to win the game if it came running heads.

If there is still a chance at least Z occurrences of heads in Y coin tosses appears OR Z appearances have already occurred, the following requirement must be met

current bankroll >= (min final bankroll needed)/(2^j)

where j = max(0,min (#remaining tosses, Z - #heads already seen))

So in this instance, Z = 3, min final bankroll = 200.

I think that's the requirement anyways.

nitro · Dec 23, 2009

Quote from nitro:

Seems to work.

I am more interested in understanding why $37.50 works and then $25 $50 $75. Does any other starting bet work with the right triplet of betting after that? What if the starting number is $160 and you have to get to $320? What is the general equation for the first number, and then for the resulting bets? What if there were n trials instead of 5?

Was $37.50 just a lucky guess?

$37.50 is awful close to 2^5 + 5 = 37. There are 2 outcomes and five trials, so one can understand why maybe 2 and 5 are there, but why this particular equation? I still don't see how to come up with $37.50 except by guessing.

nitro · Dec 23, 2009

Quote from KarateChop:

No, it was not a lucky guess. I started with the fact that if you lost the first 2 tosses, you still needed to be able to win the game if it came running heads.

If there is still a chance at least Z occurrences of heads in Y coin tosses appears OR Z appearances have already occurred, the following requirement must be met

current bankroll >= (min final bankroll needed)/(2^j)

where j = max(0,min (#remaining tosses, Z - #heads already seen))

So in this instance, Z = 3, min final bankroll = 200.

I think that's the requirement anyways.

That seems plausible. It is interesting that you decided to sort the outcomes by two initial possibilities. Was that a lucky guess, or is that also based on some sort of analysis or intuition/experience?

I guess starting from the first four possible two combination is a good start.

my7tvette · Dec 23, 2009

Quote from KarateChop:

No, it was not a lucky guess. I started with the fact that if you lost the first 2 tosses, you still needed to be able to win the game if it came running heads.

If there is still a chance at least Z occurrences of heads in Y coin tosses appears OR Z appearances have already occurred, the following requirement must be met

current bankroll >= (min final bankroll needed)/(2^j)

where j = max(0,min (#remaining tosses, Z - #heads already seen))

So in this instance, Z = 3, min final bankroll = 200.

I think that's the requirement anyways.

Well done Chop (unless the parameters change again). Intuitively, it would make sense to bet the largest possible amount early that would still leave you the minimum amount necessary if you have the worst possible start (two tails). If you lose twice, you have to bet it all each time; if you win twice, just bet whatever you need to reach $200 if the next flip is a head. If you split the first two flips, changing your bet to $50 again ensures that you will not run out of $$ if your next flip is a loser.

sjfan · Dec 23, 2009

No one has the right solution so far though a few might be on the right track.

Let me clarify a few things since there are points of confusion:

(1) You win the game when you got 3 heads (not necessarily in a row). You lose when you got 3 tails (not necessarily in a row). Either case must be true by the 5th turn, but one can be true before then (at which point the game terminates)
(2) The game itself is fair. But that's not the point. You can't have a positive expected value (this is also a hint) The point is to structure your betting so that you double your initial bankroll if you happen to win. How often you win or what your expectation is not really relevant
(3) You can bet any amount (or none at all, at the each turn), but no more than what you have on hand
(4) The solution will actually come out of knowing exactly what to bet in each case at each betting point. There's nothing Fibonacci about it. Likewise, any simple doubling down type of strategy will not work (remember - the game is both fair and finite).

A little motivation - this brain teaser isn't entirely irrelevant to trading (in the boarder institutional sense). Some of you might notice (and this is in itself a hint - part of the point for this interview question is to see whether the candidate make this mental connection) that is isn't that different from hedging a very exotic option

(Martingoul, if you happen to be reading, you don't get to publish a solution!)

Quote from nitro:

Where is the rule for the amount to bet at each turn?

sjfan · Dec 23, 2009

Chop, you are definately on the right path. You are noticing a key requirement here. But you aren't exactly right yet.

If you want to keep going, my hint (in addition to my post previous to this) is to actually chart out all the ways the game can progress (it's not that much) and see how you might apply your insight in a more... specific manner.

I will post the full solution after xmas! (sorry, I got a lot of family stuff to attend to but I promise to post a nicely formatted one with charts and stuff but it will take some time to work it out)

Quote from KarateChop:

No, it was not a lucky guess. I started with the fact that if you lost the first 2 tosses, you still needed to be able to win the game if it came running heads.

If there is still a chance at least Z occurrences of heads in Y coin tosses appears OR Z appearances have already occurred, the following requirement must be met

current bankroll >= (min final bankroll needed)/(2^j)

where j = max(0,min (#remaining tosses, Z - #heads already seen))

So in this instance, Z = 3, min final bankroll = 200.

I think that's the requirement anyways.