Actual interview brainteaser at a top flight shop

Yeah, I got no excuse for this. I should have paid more attention to the post rather than skim through them quickly trying to catch up on all the ones that accumulated overnight.

In another news, I would argue that this is nothing like the kelly criterion solely due to the fact that is a fair game with an expectation of zero.



Quote from sprstpd:

Hey sjfan,

First you give us the incorrect rules for the game and then tells us that the correct answer is incorrect. Hopefully you were not the interviewer for this very question because you would have some very confused applicants. Do you double check your prices before submitting orders? Were you involved in any of these incidents below? Just curious.
More...
 
By the way - in the actual interview where this was deployed (I wasn't on either side of that desk), the candidates who solved the question correctly would then be asked to write a script (excel and/or vba, matlab, or whatever the candidate is familiar with) that solves for a general case of winning on n-number of heads and losing on n-number of tails.

Quote from Pension_Admin:

Hi sjfan, thanks for the brainteaser. It's fun and it help keep our brain sharp for the ultimate brainteaser--how to double your capital in the market within a year.

Merry Christmas!
More...
 
Quote from sjfan:

By the way - in the actual interview where this was deployed (I wasn't on either side of that desk), the candidates who solved the question correctly would then be asked to write a script (excel and/or vba, matlab, or whatever the candidate is familiar with) that solves for a general case of winning on n-number of heads and losing on n-number of tails.
More...

Something like this?
 

Attachments

Quote from sjfan:

Yeah, I got no excuse for this. I should have paid more attention to the post rather than skim through them quickly trying to catch up on all the ones that accumulated overnight.
More...

I was just trying to give you a hard time. I enjoyed working on the problem and came up with the $37.50, $37.50 answer independently. Then I went through all the posts to see if I was correct and then I wasn't correct, and then I was correct. What a rollercoaster for my ego. The n-general case will be interesting to think about. Happy Holidays!
 
Does this work? I only tested n = 2 and n =3

Max heads/tails = n
Goal = W
Initial Bankroll = X

Bankroll ith roll = Xi
Bet ith roll = Bi
Max heads remaining ith roll = Hi
Max tails remaining ith roll = Ti

Greatest increase with consecutive wins = (2^n)
Lowest allowable bankroll allowing possible win with n consecutive heads = W / 2^n
Longest string of losses possible on First Roll = (n - 1)

Min to win on ith roll = W - Xi

Betting Schedule:

i <= n - 1: Bi = (X - (W / 2^n)) / (n - 1)
i > n -1: Bi = Min(W - Xi, Xi)

The easiest way to program it would be to have a recursive function flipping the coin keeping track of the roll i, Hi and Ti, Xi. The global variables would be n, W, X and the output would be all of the above and Bi.

I'm too lazy to put the above in code but it's not difficult.
 
Quote from sjfan:

... that solves for a general case of winning on n-number of heads and losing on n-number of tails.
More...

I can't stay away! Sjfan, I started thinking about this for a minute and I think this is unclear. I don't think you mean this literally or the game is not well defined, if n=4 and you get 3 heads and 2 tails you haven't won or lost.

But assuming you mean there can be an arbitrary number of rounds (T) and you lose if you don't win, my general solution for a problem like this starts with a function that works backwards through the tree of outcomes and calculates the minimum account needed as a function of remaining heads you need to win and rounds left to play. You only need to fill in the nodes where you have won or it is still possible to win, the other ones don't affect the outcome.

Like:
W(0,any t) = 200
W(1,1) >= 100
W(1,2) >= 150
and so on.

Then work foward and determine the bet sizes. From the beginning say you have:
W(N,T) = 100
W(N,T-1) >= X
W(N-1,T-1) >= Y

Where X and Y were determined in the first step. So you need at least X if the first flip is a tail and Y if the first flip is a head, then the first bet must be at least Y-100 and no more than 100-X. Then you can work through each node of the problem the same way and get your bet as a function of remaining heads needed and rounds to play.

The min and max bets at each node were the same in the original problem so there was a unique solution, I don't know if that is true in the general case. My hunch is that it is as long as you are starting with 100 and aiming for 200, but I am not sure.

Also, the first problem was not path dependent (so at each node the bet only depended on the total heads up to that point, not the sequence of flips to get there), and I am assuming that is still true but I am not 100% sure. I know the minimum amount required at each node is not, but if it is possible to get to each node with a different bankroll ( where W(HHT) is not equal to W(HTH) for example) then the betting strategy will have to account for that.
 
Quote from MustPlayOptions:

Nevermind, for i > n-1 there needs to be an adjustment based on how many heads and tails are left...

Are you positive this can be solved for any n?
More...

Definitely not uniquely. Easy example, 5 flips as in the orginal problem, n=5. You only care about the case where you get 5 heads, all others lose and don't affect the answer. Then any strategy where the 5 bets total $100 is a solution.

I guess I just answered my own question from the last post - my hunch was wrong, the min required bet is not always equal to the max required bet.
 
Quote from black diamond:

Definitely not uniquely. Easy example, 5 flips as in the orginal problem, n=5. You only care about the case where you get 5 heads, all others lose and don't affect the answer. Then any strategy where the 5 bets total $100 is a solution.

I guess I just answered my own question from the last post - my hunch was wrong, the min required bet is not always equal to the max required bet.
More...

I was using the definition of n as sjfan used it where n-heads and n-tails define the game.

I.e. when n=3 you need to get 3-heads before you get 3-tails so the maximum number of trials i is 5

So when n=4 you need to get 4-heads before you get 4-tails so the maximum number of trials would be 7.

My algorithm above works for n=1 to n=3 but breaks down when n=4. It works if you 3 straight heads or 3 striaght tails for the first few flips. The problem is if you end up using 2-heads and 1 tail in the first 3 flips.

If it' possible to get a general solution - you need something equivalent to looking at the initial few bets that will account for differing numbers of wins and losses based on a given bankroll. That's why I don't think it's possible.
 
You must log in or register to reply here.
Back
Top