Funny Quant story for Quant Apply @ Morgan Stanley

[Wallstyouth]

Just relaying a story thought many here might find it interesting:

<Batman28>
I actually happend to interview at Morgan Stanley quant trading team in London back in July with one of their top guys who reports directly to Yazid Sharaiha - their global head of quant trading.. I remember one of the questions that he asked me which I found ridiculous..

this is what he basically presented: imagine 3 cups and under one of them is a coin - and you have to guess under which the coin is sittin under.. assume the cups are numbered 1, 2 and 3.

now let's suppose you choose one of the cups e.g. 2. He then asks given that you choose any of the cups (2 in our example) and he takes one of the remaining cups away (not the one you chose), and if you had a chance to change your decision, would you stick to the cup you initially selected (i.e. 2)?

I immediately said yes. anyone with my mindframe would also stick to their original choice - I won't write an essay why.

the 'right' answer of course STATISTICALLY, as he stated, is you should swap and change your decision. i.e. if you stick with ur decision then 1/3 x 1/2 = 0.16.. but if you switch (implying from the start the coin was under one of the other cups) then 2/3 x 1/2 = 0.33.. i.e. higher probability.

I argued with him that this form of statistical thinking in dealing in the markets is a joke - and he agreed somewhat - but he said if they have a "quantitative/statistical MANDATE for clients" then they have to follow it and stick to it..

I'm not really surprised this is now happened. it made me think how some of these quant groups 'overfit' life with maths and ignore common sense at times.. i remember something one successful trader I met once said - "we use techniques we cannot explain but they seem to work".. just like the successful gamblers before there was statistics.. in other words, anything that can be explained (take statistics) doesn't ACTUALLY WORK.

[Wallstyouth]

When there are 3 cups, there's a 1/3 chance you are right and 2/3 that you are wrong. Once one cup is removed, it's now 50/50 but only so if you actually make the switch. Otherwise, you are really sticking to your old choice which is STILL 1/3 correct, 2/3 incorrect.

Pretty interesting : Monty Hall problem - Wikipedia, the free encyclopedia (http://en.wikipedia.org/wiki/Monty_Hall_problem)

[Adam]

There seems to be an important part of the story missing here. Namely, when the questioner takes away one of the cups after the first guess, is it a given that the cup taken away does NOT have the coin? If it is, then it is clearly to your advantage to switch. The odds of picking the right cup on the first try is 33%, which means the odds are against you having picked correctly the first time. However, of the two remaining cups, you know that at least one does not have the coin, and that one cup is eliminated from the running. That means that the remaining cup, the one not chosen first, has a 50% chance of containing the coin. Your odds are better going with the second cup than sticking with the first guess.

Even if you were to argue that sticking with the first cup has an equal 50% chance of housing the coin (I disagree, but let's pretend for now...) you still would have no incentive to stick with the first cup, since the odds are even that the coin's in the other cup. So in the second case, you might as well switch because it makes no difference, and in the first case, odds are in your favor when you switch. Why, then, would you want to stick with the first cup?

[Vic_Siqiao]

many probability problems are just ridiculous in reality.

[Euler]

The Monty Hall problem? That's one of the most famous problems in probability, ever! I don't see how any aspiring quant could NOT know the answer to that one!

[doug reich]

What's actually really funny about the story is his diatribe about the model not fitting life... however if you just PLAY the game (which is very easy to do), you see immediately that the math works out! (That was the best way to persuade my boss the math worked.)

[samiam]

Looks like the interviewers have modified the problem. Used to be about a game show with doors and a prize behind the door.

Now it's cups and coins. Tricky tricky.

[JamesHH]

It fooled me, but it was not stated carefully enough: If your "opponent" does not know what cup the coin is under, switching makes no difference.

[jepfr1210]

This is like the question in the movie "21" when the professor first met the main character in his class.

[IlyaKEightSix]

Easiest way to solve this is to take this to the extreme.

Let M (and I use M for a reason...OR folks know why) be a very large number of doors.

Behind one of these doors is the prize. All of the other doors are empty.

You select a door without opening it, and then M-2 doors are opened, leaving the door with the prize, and another door without it.

The probability that you chose the correct door on your first try is 0. Meaning that the probability that the prize is behind the other door is 1.

So you should always switch.

Now if the person removing the cup DOESN'T know which cup the coin is under, THEN it makes no difference. However, if your choice influences the host's behavior, then you should always switch.

[cstassen]

The funniest part of it all is, that everyone in this thread except IlyaK86 who speak about the solution don't get it right! one should almost use this to earn money!

If you always switch -> 2/3 probability

If you never switch -> 1/3 probability

If you randomize switch/no-switch -> p probability, p is in [1/3,2/3]

[samiam]

Just seems to work out with the stats, but not sure if it actually plays out like this in real life.

You take all the possible outcomes, they all equal to one.

So statistically, you choose one cup out of three at first, you have 1/3 chance.

Leaving 2/3 chance of one of the other two cups being right.

Well, if the guy removes one of the two cups you didn't choose, since these two cups belong to the 2/3 out of 1 probability, statistically you switch because the remaining cup you didn't choose belongs to the 2/3 set.

Yes, I get how it works out in stats, but for some reason, I have a hard time believe if you switch, you would have a twice as higher likely chance of being right than if you didn't switch.

[cstassen]

Three outcomes:

you choose the right cup in the first go - if you switch, you will no matter what be wrong.
you choose wrong cup nr1 - if you swith, you will no matter be right
you choose wrong cup nr2 - if you swith, you will no matter be right

so two outcomes you're right, one you're wrong. makes the prob 2/3.

another conundrum for you to consider

you have three drawers. one have to gold coins in it, another has one gold and one silver, the last one has two silver. You open a random drawer, take ONE coin up without seeing the other one. You notice the one you picked up is a gold coin.

What is the prob that the other coin in the same drawer is a gold coin too??

Just seems to work out with the stats, but not sure if it actually plays out like this in real life.

You take all the possible outcomes, they all equal to one.

So statistically, you choose one cup out of three at first, you have 1/3 chance.

Leaving 2/3 chance of one of the other two cups being right.

Well, if the guy removes one of the two cups you didn't choose, since these two cups belong to the 2/3 out of 1 probability, statistically you switch because the remaining cup you didn't choose belongs to the 2/3 set.

Yes, I get how it works out in stats, but for some reason, I have a hard time believe if you switch, you would have a twice as higher likely chance of being right than if you didn't switch.

[cstassen]

and if you don't believe it, play the games 2000 times - 1000 switch, 1000 don't switch. if the first one doesn't come out to somewhere between 60% and 73% winnings, and the second between 27% and 39%, i'll give you ten dollars, but if it DO happen to be in these intervals, you give me one dollar! Want to take on the bet? Could be funny actually, I'm on if you are!!!

Just seems to work out with the stats, but not sure if it actually plays out like this in real life.

You take all the possible outcomes, they all equal to one.

So statistically, you choose one cup out of three at first, you have 1/3 chance.

Leaving 2/3 chance of one of the other two cups being right.

Well, if the guy removes one of the two cups you didn't choose, since these two cups belong to the 2/3 out of 1 probability, statistically you switch because the remaining cup you didn't choose belongs to the 2/3 set.

Yes, I get how it works out in stats, but for some reason, I have a hard time believe if you switch, you would have a twice as higher likely chance of being right than if you didn't switch.

[doug reich]

Just seems to work out with the stats, but not sure if it actually plays out like this in real life.

...

Yes, I get how it works out in stats, but for some reason, I have a hard time believe if you switch, you would have a twice as higher likely chance of being right than if you didn't switch.

I'm telling you, go to your friend and play it verbally. (Person A: OK, I'm thinking of a number between 1 and 3. Person B: 2? Person A: It's not 1. Person B: ____ ) and see how often person B gets it by doing one strategy or the other. It becomes fairly obvious that person B is being told which one it is most of the time.

[doug reich]

another conundrum for you to consider

you have three drawers. one have to gold coins in it, another has one gold and one silver, the last one has two silver. You open a random drawer, take ONE coin up without seeing the other one. You notice the one you picked up is a gold coin.

What is the prob that the other coin in the same drawer is a gold coin too??

It's the same game: the probability the coin came from the first draw given you picked a gold coin is 2/3 (2 of 3 gold coins live there), and from the second drawer, 1/3. Or,

P( 2nd coin is gold | 1st coin is gold ) = P( 1st coin is gold | 2nd coin is gold ) P( 2nd coin is gold ) / P(1st coin is gold) = 1 * (1/3) / (1/2) = 2/3

[cstassen]

doug, now you've spoiled it - it was a game for samiam! :) it was obvious that you had understood it before as well!

It's the same game: the probability the coin came from the first draw given you picked a gold coin is 2/3 (2 of 3 gold coins live there), and from the second drawer, 1/3. Or,

P( 2nd coin is gold | 1st coin is gold ) = P( 1st coin is gold | 2nd coin is gold ) P( 2nd coin is gold ) / P(1st coin is gold) = 1 * (1/3) / (1/2) = 2/3

[doug reich]

doug, now you've spoiled it - it was a game for samiam! :) it was obvious that you had understood it before as well!

Sorry I was just in a probability course and wanted to remind myself I could do the math... :)

[IlyaKEightSix]

The funniest part of it all is, that everyone in this thread except IlyaK86 who speak about the solution don't get it right! one should almost use this to earn money!

If you always switch -> 2/3 probability

If you never switch -> 1/3 probability

If you randomize switch/no-switch -> p probability, p is in [1/3,2/3]

Well actually I saw a youtube explanation (which made me realize the entire source of confusion), and the entire cause of confusion is this question:

Does your choice influence the host's behavior?

If the host is absolutely not allowed to remove the door with the prize behind it, then your decision influences his behavior. If he IS allowed to remove the door with the prize behind it, however, then switching is meaningless.

It isn't so much the question of the math and probabilities and such as it is understanding the problem. Almost all famous probability problems arise from the fact that you obtain different answers according to different procedures, such as Bertrand's paradox, and this problem:

I have two cans. One contains a black ball, the other contains a black ball and a white ball.

What's the probability I obtain a white ball?

The answer depends on my procedure. If I close my eyes, reach into a can, and pick out the first ball I touch, the probability is one fourth. But if I dump the balls out, close my eyes, and pick up a ball, the probability is one third.

The math behind the problem has only one solution per given instance per given procedure. But the reason we have crashes in the financial markets isn't that the math is wrong--it's that the underlying logic was flawed.

[cstassen]

the question said the host opens the door which has no price behind it -that's not a source of confusion.

also don't believe you're right. Fx the Allais paradox - to identical situations don't get treated equally, and that's because people are stupid! after you explain it to them, they get it. i think it's the same with finance - 9/10 are financial illiterates! if you go to interview at Goldman, Stanley whatever, they are trying to assess if you have THAT sense of market/business understanding, no matter what your degree is! An example:

100 people with white and black hats are to be executed. They have to stand in a line, and the execution will start from the back. nobody knows what colour their hat is, all they know is what the hats IN FRONT of them are. The executioner asks the guy in the back what colour his hat is - if he says the right color, he will be spared, and the executioner moves on to the next person in the line. What is the maximum number of people the group can save with certainty, if everybody acts in their own interest but if the group can collaborate?

Well actually I saw a youtube explanation (which made me realize the entire source of confusion), and the entire cause of confusion is this question:

Does your choice influence the host's behavior?

If the host is absolutely not allowed to remove the door with the prize behind it, then your decision influences his behavior. If he IS allowed to remove the door with the prize behind it, however, then switching is meaningless.

It isn't so much the question of the math and probabilities and such as it is understanding the problem. Almost all famous probability problems arise from the fact that you obtain different answers according to different procedures, such as Bertrand's paradox, and this problem:

I have two cans. One contains a black ball, the other contains a black ball and a white ball.

What's the probability I obtain a white ball?

The answer depends on my procedure. If I close my eyes, reach into a can, and pick out the first ball I touch, the probability is one fourth. But if I dump the balls out, close my eyes, and pick up a ball, the probability is one third.

The math behind the problem has only one solution per given instance per given procedure. But the reason we have crashes in the financial markets isn't that the math is wrong--it's that the underlying logic was flawed.

[IlyaKEightSix]

cstassen, I believe the answer to your question is 99. I remember such a question posed by my math major friend in college, and I believe the person in the back of the line gives a certain signal if there are an odd amount of white hats, and the other signal if there are an even number of hats, and then the next person can just count and decide what color his hat is, and then it bubbles up until everyone but the last person knows what color their hat is.

[alain]

100 people with white and black hats are to be executed. They have to stand in a line, and the execution will start from the back. nobody knows what colour their hat is, all they know is what the hats IN FRONT of them are. The executioner asks the guy in the back what colour his hat is - if he says the right color, he will be spared, and the executioner moves on to the next person in the line. What is the maximum number of people the group can save with certainty, if everybody acts in their own interest but if the group can collaborate?

There is a lot of ambiguity in this problem. 100 people with black and white hats, do they know the total amount of black and white hats? What type of collaboration? If they are only allow to say WHITE or BLACK, there is no room for collaboration at all.

You need to give more details. In an interview, your ability to discover or ask about those details is also measured. That's part of your thinking process.

[John]

The way the problem is stated, it is totally irrelevant what color of hat the persons in front of his/her are wearing. Like Alain said, you don't know the total of either color of hat, so you cannot get any hint to what he/she him/herself is wearing.

[doug reich]

The way it's stated, it sounds like you could very easily save all the people: each person tells the person in front of them what color that person's hat is. The last two people switch, and the former "last" person is told what color his hat is. "Collaboration"!

[John]

or..... why not just switch hat with the person in front and then swith it back :)

[cstassen]

maybe i was unclear - you can hear what the person behind you says. sorry for leaving that out.

they are allowed to collaborate in the sense that before lining up, they can decide on a strategy for what each person should say. each person should only say "white" or "bklack" - they can't both say what their own hat is and also say something to the guy in front of you. if he says what is on top of his head, he won't get killed.

and that is all you need, no info about total number of white versus black is needed

[IlyaKEightSix]

John, with my solution, you don't need to. The strategy is this: the person in the back will say white if he sees an even number of white hats, or black if he sees an odd number of white hats. Say there were 50 white hats and 49 black hats in the line ahead of him.

The person in the back (let's call him person 1) will say white.

Then person 2 will count the white hats ahead of him, knowing that there are an even number of white hats. If he counts the 50 white hats, he has a black hat, and if he counts 49 white hats, it means he has a white hat.

Now this problem, of course, has some unrealistic human assumptions in that the people will be able to keep perfect memory of how many white and black hats there were called out already.

But given this assumption, this strategy is guaranteed to save all but one person, and then that last person still has a 50% chance of making it out alive.

[alain]

this strategy is guaranteed to save all but one person, and then that last person still has a 50% chance of making it out alive

When you say the last person, you are talking about the first one to call BLACK or WHITE, correct?

[IlyaKEightSix]

Yes I am. Once again, I've seen this problem before. Though I hope this forum shows enough of my aptitude so I can get into Goldman Sachs this recruiting season.

[alain]

dude, why do you have this love for Goldman? What about any other place?

[cstassen]

Ilya, your solution is right, but one actually doesn't have to remember everything that has been said priorly. Think it over again...

Alain: because we are the best of course!

[alain]

Alain: because we are the best of course!

You are already in. Poor Ilya is not in yet but he will stop short of nothing to join GS.

[cstassen]

If you want to swim with the big boys, don't jump into the small pool :) I agree, though!

You are already in. Poor Ilya is not in yet but he will stop short of nothing to join GS.

[IlyaKEightSix]

Second choice? JPMorgan Chase because they're the only other bank really remotely above this whole subprime mess, but they're glutted with Bears employees, so my chances seem slim there. But it's a far second choice.

Third choice? Lehman Brothers. Simply because a girl I knew from high school has interned there twice, and she knows what the heck she's doing and her advice to me has always been good (on an off-topic note, I miss her like hell...I swore I'd catch up in college and have fallen further behind it seems).

After that, I'm thinking Deutsche Bank or Group One. Deutsche seems another popular interning spot for friends of mine, so I'm guessing it's decent, and Group One has a lot of Lehigh alums.

Now, why Goldman?

Because Goldman Sachs cleans house. Their "where would I fit in best" job application was pure genius, and if there was one merit to this subprime/credit crisis, it's to show which firms are worth working for, and which are run by lemmings and imbeciles that probably wouldn't be able to make heads or tails of their own quantitative departments.

And because I know what I could do with the money and power earned by people at Goldman Sachs that prove themselves through hard work and dedication. Alternative energy. Zero emissions transportation. K-12 education in math, science, engineering, economics, and finance (keep that MfA going, Jim Simons!).

But first and foremost, I need to prove myself to myself, that I can leverage my education to make good of myself. And when I make something more of myself than I already am, I want to see to the fact that America makes use of its potential a lot more than it does.

Came into America at 4 years old, $15 and two suitcases between me, my mother (a piano teacher), and my dad (a real estate broker). I've come this far, as a result of my own merits. And I believe Goldman matches my philosophy of no shortcuts, merit, talent, dedication, motivation, and hard work.

And no, this isn't a sales pitch. It's just that I've never gotten anywhere with glib, and only recently read a book on how to do it slightly better (Dale Carnegie's book), so I've become so used to getting anywhere with my own merits that I don't want it any other way.

[IlyaKEightSix]

Ilya, your solution is right, but one actually doesn't have to remember everything that has been said priorly. Think it over again...

Alain: because we are the best of course!

I didn't remember everything. I just remembered the question and how much I was trying to bend my brain around it the first time.

I remember the times I did a really great job, but more than that, I remember the times when I blundered, and learn from them.

[alain]

<offtopic>
Ilya, It looks like you only know about big banks but there is a lot more out there. GS is not the only one that clean house. It happens it's the only one you hear about. You should try to research or find out more about other places.

At the same time, keep the rhetoric and the "fan boy speak" down. There are people that had it worse than you and don't advertise it.

[doug reich]

Ilya, your solution is right, but one actually doesn't have to remember everything that has been said priorly. Think it over again...

You just need to remember whether there are odd or even number of blacks hats (hehe) and whether your position in line is odd or even.

[cstassen]

No you don't you have to hear what the guy behind you says, and be able to see in front of you. that's it!

You just need to remember whether there are odd or even number of blacks hats (hehe) and whether your position in line is odd or even.

[finmathguytr]

Ilya, your solution is right, but one actually doesn't have to remember everything that has been said priorly. Think it over again...
since all prisoners are allowed to talk to each other and to set a strategy, mine would be this: the first one to be executed is to say the color of hat in front of him, so that the second shall know what to say. if there is n person, we have 1/2 chance to save all prisoners and another 1/2 to save n-1.

[IlyaKEightSix]

The people are lined up in alternating colored hats.

Congratulations, everybody dies.

[finmathguytr]

The people are lined up in alternating colored hats.

Congratulations, everybody dies.

i don't see how this would happen. second person is not to say the color of the hat of the one ahead of him. this is only for the first one. the second will just say what he heard. if he heard black, then his hat color is black and vice versa.

[cstassen]

i don't see how this would happen. second person is not to say the color of the hat of the one ahead of him. this is only for the first one. the second will just say what he heard. if he heard black, then his hat color is black and vice versa.


You wouldn't get a job from this answer, that's for sure! What's the third person to do? in this way, you save 50% max! IlyaK8 did the right solution, although his reasoning was not perfect!

advice: think the solution through before you answer it - one thing is to come up with a solution, another one is to look it over, test if its correct and THEN redo it if it's wrong (which it is 9/10 times). that is when you have done well at an internship

[finmathguytr]

i half-read the problem sorry. there was another problem on hats, at which once someone tells the color of the hat right, then the rest is to be saved. i mixed parts of each in one another while answering, which is exactly one of the mistakes that a job-applicant should not do, i think =).

[samiam]

since all prisoners are allowed to talk to each other and to set a strategy, mine would be this: the first one to be executed is to say the color of hat in front of him, so that the second shall know what to say. if there is n person, we have 1/2 chance to save all prisoners and another 1/2 to save n-1.

You are correct. But they have to agree before they line up that starting from the back of the line, the even numbered guys agree to say what the odd number guys said, while the odd number guys will just say what the even number guys hat colors are. As soon as they line up they have to make mental note whether they are odd or even.

The odd number guys are screwed. If they wear alternating colored hat, with certainty you save 1/2 of all prisoners and n=even, 1/2*(n-1) if n=odd.


And they are only allowed to say one thing after they line up, either "white" or "black".

Example just use 10 guys to break down the problem.

Because the last guy calls out 2nd guys hat color, he has 1/2 chance.

2nd guy calls out what last guy said. He is saved for sure.

3rd guy calls out calls out 4th guys hat color, he has 1/2 chance.

4th guy calls out what 3rd guy said. He is saved for sure

5th guy calls out calls out 6th guys hat color, he has 1/2 chance.

6th guy calls out what 5th guy said. He is saved for sure.

7th guy calls out 8th guys hat color. He has 1/2 chance.

8th guy calls out what 7th guy said. He is saved for sure.

9th guy calls out 10th guys hat color. He has 1/2 chance

10th guys calls out what 9th guy said. He is saved for sure.

[samiam]

The people are lined up in alternating colored hats.

Congratulations, everybody dies.

If alternating hats, exactly half die, and they will be the guys who are odd numbered starting from the back where the warden does his execution yes or no.

[samiam]

This is like the most intense brain solver type of question I have ever heard.

FYI, there is a way to save all of the prisoners. A guy doing his PhD at UCSB actually did his research thesis on this problem and the implications of his thesis has relevance to algebraic coding theory or something like that.

You should look it up if you're curious. I was looking at the answer to the problem, and maybe I didn't think about it long or hard enough, but just looking at it for a little while, I felt like I needed a lobotomy. It is way intense.

You are supposed to answer a brain teaser at an interview that a guy did his PhD thesis on. Whoaaah.

There is also a way to save 99 of the 100 too. I guess the last guy takes a 50/50 shot while based on the last guys answer (everyone has to hear it), each guy in front just counts the number of odd or even white hats in front of him and decides if he is white or black.

Anyways, these problems are intense. What happened to how many golf balls you can fit in a plane or how many manholes are there in NYC.

[IlyaKEightSix]

Oh, you mean like how many candy corns are in a jar? A bit of counting and then applying a sanity test and I got second place and won a better prize than first. The first prize was the candy corns (ugh) and the second prize was a whole bag of fun-sized choco bars full of babe ruths and butterfingers and other such yummies ^_^

(They're procedurally trivial BTW)

The entire point of a brain teaser is like parallel parking for your driving test. Can you think? Can you establish a good process even if you don't arrive at the best answer? Can you get the *right* answer?

Cstassen, in my humility, I have to admit that when I first saw that problem, I was absolutely stumped. But the key is to learn from your errors and build on them, and to be always ready to say "I don't know".

[cstassen]

If alternating hats, exactly half die, and they will be the guys who are odd numbered starting from the back where the warden does his execution yes or no.

samiam, you're not getting it right. all they have to do is say the even-uneven strategy as ilya describes. that's it, no other agreement is needed

[samiam]

samiam, you're not getting it right. all they have to do is say the even-uneven strategy as ilya describes. that's it, no other agreement is needed


Oh, I was just replying to Ilyak8's reply to Finmath's theory of way to solve the problem with only a minimum of 1/2 of the prisoner's getting executed with certainty. He said, if they were to switch the order of the hats with alternating B/W/B/W hats, then they would all die. I worked the problem out and verified Finmath's answer, and found out that switching the order of the hats would lead to exactly 1/2 being executed (and not all of them) and if the orders were not switched then there is at least a 1/2 being executed.

I saw the explanation for variation's of this problem. The 1/2 certainty was not covered but they showed explanations of 99/100 being saved with certainty and 100/100 being saved with certainty. So you are right about 99 out of 100 being able to be saved. B

But there is also a way to save all 100 of the prisoners, and looking at the answer to that one, if anybody in an interview were to be able to on his own come up with that answer, they would be statistically a mental outlier IMO. Because it took the guy to come up with that answer a PhD thesis to explain how to do it.

[samiam]

Oh, you mean like how many candy corns are in a jar? A bit of counting and then applying a sanity test and I got second place and won a better prize than first. The first prize was the candy corns (ugh) and the second prize was a whole bag of fun-sized choco bars full of babe ruths and butterfingers and other such yummies ^_^

(They're procedurally trivial BTW)

The entire point of a brain teaser is like parallel parking for your driving test. Can you think? Can you establish a good process even if you don't arrive at the best answer? Can you get the *right* answer?

Cstassen, in my humility, I have to admit that when I first saw that problem, I was absolutely stumped. But the key is to learn from your errors and build on them, and to be always ready to say "I don't know".

Yeah the teasers I mentioned were of the mgmt consulting variety where you don't have to be too much of a whiz to solve. I guess I tried to pick the easiest ones I could think of.

There were also how many times do you have to weigh using a balance scale to find out which balls out of 6 balls weigh differently. Two princes have to ride their horse on 3 day trek to a city, and the first horse that gets there inherits the throne to the kingdom. On the 2nd day of the horse, all of a sudden they ride as slow as possible. Why did they do this all of a sudden. I guess these one take an iota of more thought.

I also got the three doors with the prize on a commodities assistant trader interview along with with would you jump down into a 12 feet deep pool from 12 stories. Stuff like that. Didn't really see the connection between being able to solve these problems easily with trading well. I knew a guy who was a whiz at these teasers but he couldn't hack it as a trader and went into banking. I guess for quants it makes sense though.

[cstassen]

Can you show a link to that answer? 'Cause I'd say that it is impossible to save everybody (non-full rank!)

Oh, I was just replying to Ilyak8's reply to Finmath's theory of way to solve the problem with only a minimum of 1/2 of the prisoner's getting executed with certainty. He said, if they were to switch the order of the hats with alternating B/W/B/W hats, then they would all die. I worked the problem out and verified Finmath's answer, and found out that switching the order of the hats would lead to exactly 1/2 being executed (and not all of them) and if the orders were not switched then there is at least a 1/2 being executed.

I saw the explanation for variation's of this problem. The 1/2 certainty was not covered but they showed explanations of 99/100 being saved with certainty and 100/100 being saved with certainty. So you are right about 99 out of 100 being able to be saved. B

But there is also a way to save all 100 of the prisoners, and looking at the answer to that one, if anybody in an interview were to be able to on his own come up with that answer, they would be statistically a mental outlier IMO. Because it took the guy to come up with that answer a PhD thesis to explain how to do it.

[cstassen]

Samiam, by the way, everybody does not have to hear the first mans reply - they only need to hear the guy behind them's answer! Think it through

[samiam]

Can you show a link to that answer? 'Cause I'd say that it is impossible to save everybody (non-full rank!)

Definitely possible dude. By the way, these guys are prisoners. Unless they were scientist prisoners in a Siberian boot camp imprisoned for colluding with spies to reveal state secrets, I bet my life that no 100 prisoners would ever come up with a way to save all of their own asses!

Hat puzzle - Wikipedia, the free encyclopedia (http://en.wikipedia.org/wiki/Hat_puzzle)

[cstassen]

This is a different puzzle - they can see all hats (mine only see hats in front of them), they can answer whenever instead of one at a time! and so on. but very clever solution (although clever i don't think it's that advanced - his thesis must have been a little more deep than that :D)

:dance: (dancing banana just for the hell of it)

Definitely possible dude. By the way, these guys are prisoners. Unless they were scientist prisoners in a Siberian boot camp imprisoned for colluding with spies to reveal state secrets, I bet my life that no 100 prisoners would ever come up with a way to save all of their own asses!

Hat puzzle - Wikipedia, the free encyclopedia (http://en.wikipedia.org/wiki/Hat_puzzle)

[samiam]

I hope I never have to get this kind of problem in an interview. LIke ever. Honestly, unless you get this exact problem, I have a hard time envisioning regular MFE grads unless they are Gary Kasparov's nephew to get this problem right by solving it in his head on the first time hearing it. Unless he has a sheet of paper and a few minutes or more to work it out. (I needed way more than that).

Ok, to get the 99/100 certainty, every guy in front of the last guy in line has to know not only what he says but also if he lives or dies. (Assuming the warden does the execution by going up each prisoner starting from the back, putting a gun to his head, and if the guy says black or white and gets it wrong, he pulls the trigger).

So we'll use 10 prisoners instead of 100 to make it simple.

Let's say the warden puts on 5 white hats and 5 black hats randomly on the 10 prisoners.

The last guy starts first. He will say white if he counts even number of white hats in front of him and black if he counts odd number of white hats.

Prisoner number, the color of his hat, and what he says:

#10, W, says W

(after the last guy says "White", the other 9 guys in front realize the warden didn't kill him so they know that he counted an even number of white hats and said white, but was not executed so he himself has a white hat. Now they all know there are an odd number of white hats, so that must mean there must also be odd number of black hats

#9, B, says B

(#9 counts even white hats in front and even black hats in front of him but knows #10 is white. So he must be black)

#8, B, says B

(#8 counts even white hats in front and odd black hats in front. But he knows #9 is black and #10 is white. So he knows he will be black because he adds up the three black hats he sees in front + 1 black hat called already + his own black hat = odd number of black hats)

#7, B, says B

(#7 knows there are 2 black hats and 1 white hat behind him. He counts even white hats and even black hats in front him. He know he must be black because he knows 2 black hats behind + 2 black hats in front + his own black hat = odd number of black hats

#6, W, says W

(#6 knows there are 3 black hats and 1 white hat behind him. He counts odd white hats and even black hats in front. He must be white because 1 white hat behind + 3 white hats in front + his own white hat = odd number of white hats)

#5, W, says W

(#5 knows there are 3 black hats and 2 white hats behind him. He counts even white and even black hats in front. He must be white because 2 white hats behind + 2 white hats in front + his own white hat = odd number of white hats)

#4, B, says B

(#4 knows there are 3 black hats and 3 white hats behind him. He counts even white and odd black in front. He must be black because 3 black hats behind + 1 black in front + his own black hat = odd number of black hats)

#3, W, says W

(#3 knows there are 4 black hats and 3 white hats behind him. he counts odd black and odd white in front. He must be white because 3 white behind + 1 white in front + his own white hat = odd number of white hats)

#2, B, says

(#2 know there are 4 black hats and 4 white hats behind him. He sees guy in front is white. He must be black because 4 black behind + his own black hat = odd number of black hats)

#1, W

(#1 knows there are 5 black hats behind him and 4 white hats. Duh. He must be white)



This problem will work according to whether or not the warden pulls the trigger on #10.

If he said White and he pulled the trigger, then they all know there are even number of white hats and there must be even number of black hats. If he said black and he pulled the trigger, then there are even number of white hats and even number of black hats. If he said black and he didn't pull trigger, then they all know there are odd number of white hats and odd number of black hats.

For 100 prisoners, it would be fair if the warden gave every guy a piece of paper and a pencil to keep track of the number of blacks or whites behind them.

[samiam]

This is a different puzzle - they can see all hats (mine only see hats in front of them), they can answer whenever instead of one at a time! and so on. but very clever solution (although clever i don't think it's that advanced - his thesis must have been a little more deep than that :D)

:dance: (dancing banana just for the hell of it)

Very clever answer. Took a thesis to do it. I would have never thought of it. And you're right if they didn't see the hats behind them, it's impossible to get all 100 saved.

[cstassen]

No, they only have to hear if the guy behind them calls BLACK or WHITE (if everybody stickts to the strategy of course), and be able to see all hats in front of them. No more, no less. That's the way it is! You keep getting it wrong, saying that they need to hear all other peoples replies (only need to hear the one behind him) and knowing something extra. Redo your analysis from scratch i think, do a "game tree"

[samiam]

No, they only have to hear if the guy behind them calls BLACK or WHITE (if everybody stickts to the strategy of course), and be able to see all hats in front of them. No more, no less. That's the way it is! You keep getting it wrong, saying that they need to hear all other peoples replies (only need to hear the one behind him) and knowing something extra. Redo your analysis from scratch i think, do a "game tree"

What's the extra thing they need to know?

[cstassen]

You said they need to keep track of wether people got shot or not! and that's incorrect

[samiam]

I'm not the sharpest knife in the ginzu shed. So I might be wrong. But with my solution for the 99/100 prisoners being saved, the solution works (as I worked it out). Albeit it may be unreasonable to think that all 100 prisoners must keep a tally starting from the back whether the count of black and white hats is odd or even. But it does work.

From my analysis, it seems impossible for each prisoner to guess the color of his own hat just by looking at how many black and white hats are in front of him while only knowing what the color of the guys hat behind him is.

[cstassen]

Try working on it more! Or at least try to check the other solution through!

[IlyaKEightSix]

Odd, even, odd, even, odd, even, odd, even...

That's how.

[cstassen]

One could say that the process is "a deterministic markov chain" - you only need the information about the prior guy to determine the "expectation"