|
So I'm an undergraduate first-year in NYC, and I'm looking to go into finance. Now a lot of these firms will ask you the cliche interview questions. "What can you bring to the team? What is your greatest weakness?" Blah blah blah, shit like that. However, a lot of these firms will also ask you more technical math questions.
Some institutions, like Jane Street Capital, are famous for these. They just ask you really hard math questions.
I was wondering if any of you had these. And they're not just so I can use them to see what they're like, but I think it'd be nice to get a compilation going.
For example, here are some I have:
1.) 25 horses, five lanes, no stopwatch. Find the 3 fastest horses in as few races as possible.
2.) 30 strings. Two parallel rows of 30 holes. Each of the 30 strings goes through one of the 30 holes in the first row, and then one of the 30 holes in the second row. What is the expected number of crossovers, where one string overlaps the other?
3.) 2 strings, a box of matches. Each of the strings takes an hour to burn from end to end. However, they don't burn uniformly, so one inch of the string could take 59 minutes to burn through, and the rest burns up in a minute. Measure 15 minutes of time.
Also, does anyone know what level of math they want? I made AIME in high school and got an 11, and went to a bunch of those national math competitions (ARML, HMMT, PuMAC), but there are definitely people who are better than me who have been rejected.
Anyone who actually works at Jane Street or DE Shaw or some other big and famous firm is welcome to post here. I could use literally any advice.
|
On March 29 2011 17:54 DTK-m2 wrote:
So I'm an undergraduate first-year in NYC, and I'm looking to go into finance. Now a lot of these firms will ask you the cliche interview questions. "What can you bring to the team? What is your greatest weakness?" Blah blah blah, shit like that. However, a lot of these firms will also ask you more technical math questions.
Some institutions, like Jane Street Capital, are famous for these. They just ask you really hard math questions.
I was wondering if any of you had these. And they're not just so I can use them to see what they're like, but I think it'd be nice to get a compilation going.
For example, here are some I have:
1.) 25 horses, five lanes, no stopwatch. Find the 3 fastest horses in as few races as possible.
2.) 30 strings. Two parallel rows of 30 holes. Each of the 30 strings goes through one of the 30 holes in the first row, and then one of the 30 holes in the second row. What is the expected number of crossovers, where one string overlaps the other?
3.) 2 strings, a box of matches. Each of the strings takes an hour to burn from end to end. However, they don't burn uniformly, so one inch of the string could take 59 minutes to burn through, and the rest burns up in a minute. Measure 15 minutes of time.
Also, does anyone know what level of math they want? I made AIME in high school and got an 11, and went to a bunch of those national math competitions (ARML, HMMT, PuMAC), but there are definitely people who are better than me who have been rejected.
Anyone who actually works at Jane Street or DE Shaw or some other big and famous firm is welcome to post here. I could use literally any advice.
I think this is correct:
1) 7. Race them in groups of 5. Race the winners of those groups. Then race the only 5 that could potentially be 2nd or 3rd (you can work that out, it's easy to see)
2) Err, misread the problem. I'll do it later.
3) Start one burning at one end, the other at both. After the latter burns entirely light the other end of the first. From that point until it finishes burning is 15 minutes.
|
I'm not planning on going into finance, but I have a lot of friends who interview for these sort of things. A couple of the questions they've been asked:
4) You're in the center of a circular lake. There's a wolf on the edge that runs 4 times faster than you swim. He will always take the shortest path to the closest point on the shore to your current location. How do you escape?
5) There are 100 people in separate rooms. They can talk as much as they want until they "begin." Once they begin, they are called one at a time, in no particular order, into another room. In this room is only a light switch that turns on and off a lightbulb in the room. Noone can see the lightbulb unless they are in the room, and the only thing you can do in the room is check the lightbulb, turn it on, or turn it off. How do the people know when all 100 have been called? (You can be called more than once before everyone else has gone once).
6) An explorer lands on an island run by a cult. In this cult, if you know your own eye color, you must kill yourself. There are 500 blue-eyed people on the island and 500 brown-eyed people, but obviously they don't know this. Every night there is a meeting, at the end of which, if you know your eye color you must kill yourself. Before leaving, the explorer attends one of these meetings, and says where everyone can hear "It's so nice to see another blue-eyed person" then escapes. What happens and when?
|
Responding to PJ. How do you know you dont have a starting group with the 3 best horses. Your way doesnt work since you cant assume the best horses are in different groups
|
edit: never mind, i think 7 is correct found the question and answer from another site.
+ Show Spoiler +
Race all 25 horses in groups of 5. Call the groups A, B, C, D and E. Call the winners from each of these races A1, B1, C1, D1, and E1. That's 5 races so far, and any horse who came in 4th or 5th in any race is out.
Now, race A1, B1, C1, D1, and E1 together. That's 6 races. Let's just assume that A1 wins, B1 is second, and C1 is third. That means:
(1) A1 is definitely the fastest horse overall.
(2) Any horse from group D or group E is out. (3) Any horse from group C, other than C1, is definitely out -- they lost to C1, who was third in the winners' race; thus for example, C2 is fourth fastest at best.
(4) B3 is out. He came in third to B1, thus he's at best 4th fastest overall.
Thus the only remaining horses vying for contention are A1, A2, A3, B1, B2, and C1. We know A1 is definitely the fastest. Thus race A2, A3, B1, B2, and C1 together. That's 7 races. The winner and second-place finisher of this race are the second and third-fastest overall.
|
On March 29 2011 19:00 Marradron wrote:
Responding to PJ. How do you know you dont have a starting group with the 3 best horses. Your way doesnt work since you cant assume the best horses are in different groups
Picture this:
Columns are groups of horses in fives. They are conveniently sorted from fastest to slowest from the top left to the bottom right because... The first five races give you the top runners from each group. Throw the top runners from each group in a sixth race. You now have your guaranteed fastest horse at the most top left position. The seventh race has the leftover five horses marked by the orange circles (excluding the fastest horse at the upper left corner). The two winners are the remainder of your three fastest horses.
That's just how I see it though ;p
|
OP. You created an awesome thread. I didn't even know firms asked these questions and I'm a finance major =X.
|
United States24666 Posts
On March 29 2011 18:35 eluv wrote:
4) You're in the center of a circular lake. There's a wolf on the edge that runs 4 times faster than you swim. He will always take the shortest path to the closest point on the shore to your current location. How do you escape?
What is the answer to this one? If you start 1 inch to the left side of the middle, wait for the wolf to go to the left side, then make a break towards the right side he will beat you there since .5C = pi*r < 4r.
Is it some type of spiral shape taking advantage of the wolf's position? I don't know how to show that mathematically.
|
On March 29 2011 19:37 micronesia wrote:Show nested quote +On March 29 2011 18:35 eluv wrote:
4) You're in the center of a circular lake. There's a wolf on the edge that runs 4 times faster than you swim. He will always take the shortest path to the closest point on the shore to your current location. How do you escape?
What is the answer to this one? If you start 1 inch to the left side of the middle, wait for the wolf to go to the left side, then make a break towards the right side he will beat you there since .5C = pi*r < 4r. Is it some type of spiral shape taking advantage of the wolf's position? I don't know how to show that mathematically.
IIRC if you spiral your path (or just row away from the ogre) you'll end up on the opposite side of the lake or at some point where you can just row straight toward shore and get away ;o
|
On March 29 2011 19:37 micronesia wrote:Show nested quote +On March 29 2011 18:35 eluv wrote:
4) You're in the center of a circular lake. There's a wolf on the edge that runs 4 times faster than you swim. He will always take the shortest path to the closest point on the shore to your current location. How do you escape?
What is the answer to this one? If you start 1 inch to the left side of the middle, wait for the wolf to go to the left side, then make a break towards the right side he will beat you there since .5C = pi*r < 4r. Is it some type of spiral shape taking advantage of the wolf's position? I don't know how to show that mathematically.
You just start swimming directly away from the wolf, and then you constantly turn your path to swim directly away from the wolf. You will end up spiraling, but you will slowly get closer to the edge while the wolf will never make any progress around the circle towards you.
|
On March 29 2011 19:46 Chriamon wrote:Show nested quote +On March 29 2011 19:37 micronesia wrote:On March 29 2011 18:35 eluv wrote:
4) You're in the center of a circular lake. There's a wolf on the edge that runs 4 times faster than you swim. He will always take the shortest path to the closest point on the shore to your current location. How do you escape?
What is the answer to this one? If you start 1 inch to the left side of the middle, wait for the wolf to go to the left side, then make a break towards the right side he will beat you there since .5C = pi*r < 4r. Is it some type of spiral shape taking advantage of the wolf's position? I don't know how to show that mathematically. You just start swimming directly away from the wolf, and then you constantly turn your path to swim directly away from the wolf. You will end up spiraling, but you will slowly get closer to the edge while the wolf will never make any progress around the circle towards you. (or maybe he will make progress, i havent done the math)
I still don't get it 
|
On March 29 2011 19:50 endy wrote:Show nested quote +On March 29 2011 19:46 Chriamon wrote:On March 29 2011 19:37 micronesia wrote:On March 29 2011 18:35 eluv wrote:
4) You're in the center of a circular lake. There's a wolf on the edge that runs 4 times faster than you swim. He will always take the shortest path to the closest point on the shore to your current location. How do you escape?
What is the answer to this one? If you start 1 inch to the left side of the middle, wait for the wolf to go to the left side, then make a break towards the right side he will beat you there since .5C = pi*r < 4r. Is it some type of spiral shape taking advantage of the wolf's position? I don't know how to show that mathematically. You just start swimming directly away from the wolf, and then you constantly turn your path to swim directly away from the wolf. You will end up spiraling, but you will slowly get closer to the edge while the wolf will never make any progress around the circle towards you. (or maybe he will make progress, i havent done the math) I still don't get it
Keep swimming straight, but make sure your back is to the wolf the entire time. You will be at the farthest point from the wolf the entire time and you will spiral out of the lake slowly. When you get out, he will still be across the lake from you. I don't know the math behind it though...
|
|
|
Let R be the radius of the lake.
If you're at 1/4 * R distance from the center, you swim as fast as the wolf runs if you swim in a circle.
That means that at 1/4*R - Ɛ you can swim the inner circle faster than the wolf runs the outer circle, meaning that after you've swum long enough, your distance to the outer circle is 3/4*R ( + Ɛ) , and the wolf's distance to the same spot is π*R.
![[image loading]](http://i.imgur.com/xzLjE.png)
π*R / (3/4*R) = 4π/3 = 4,1888 > 4
|
On March 29 2011 20:08 slmw wrote:Let R be the radius of the lake. If you're at 1/4 * R distance from the center, you swim as fast as the wolf runs if you swim in a circle. That means that at 1/4*R - Ɛ you can swim the inner circle faster than the wolf runs the outer circle, meaning that at 1/4*R your distance to the outer circle is 3/4*R ( + Ɛ) , and the wolf's distance to the same spot is π*R. π*R / (3/4*R) = 4π/3 = 4,1888 > 4
Thanks for the explanation, I think I get it now. So you only spiral until you are at at R/4 distance from the center and that the wolf is at the total opposite direction. Then swim straight to the shore, right ?
|
On March 29 2011 20:17 endy wrote:Show nested quote +On March 29 2011 20:08 slmw wrote:Let R be the radius of the lake. If you're at 1/4 * R distance from the center, you swim as fast as the wolf runs if you swim in a circle. That means that at 1/4*R - Ɛ you can swim the inner circle faster than the wolf runs the outer circle, meaning that at 1/4*R your distance to the outer circle is 3/4*R ( + Ɛ) , and the wolf's distance to the same spot is π*R. π*R / (3/4*R) = 4π/3 = 4,1888 > 4 Thanks for the explanation, I think I get it now. So you only spiral until you are at at R/4 distance from the center and that the wolf is at the total opposite direction. Then swim straight to the shore, right ?
No need to spiral at all.
First swim straight to the 1/4*R circle, then swim in circle until the wolf is at the opposite side of the lake and then swim straight to the freedom.
|
For the horse problem there are ways you can be slightly more efficient in your elimination, though im gonna have to test it out a bit more thouroughly on paper
If you use information about the fastest horse from previous races, you can potentially eliminate more than 2 horses per race in the first 5 races
|
Think outside the box and inside the box also for the wolf lake problem.
Know your variables. 1 human, 1 wolf.
Swim a little side to side and the wolf will run the entire distance around the lake again and again and tire itself out.
Then proceed in any direction. Remember the math solution doesn't help you if the lake is so small the wolf always catchs you; you want a solution that encompasses all possible lake sizes which the math only solves for large lakes considering the speed of a human swimming is.
|
Just tesitng the horse thing, i've found a solution with only 6 races, though i havnt checked combinatorically whether it will ALWAYS be 6 solutions, only that 6 solutions is possible
I'm gonna test worst and best case in a sec and if i get 6 each time then im pretty sure its 6
|
Ooo this thread is awesome, don't have much time so i only did first question.
1) I believe the answer is 8. Get 5 horses race em, keep the top 3 and put 2 untested horse in the mix to race again. The problem with racing the best of 5 seperate groups is that u run the risk of putting 5 of the fastest horses in the first race. Will try the rest tmr!
|
The more im working on the horse problem the more i am sure that the solution is 6
Even in the very worst case scenario, by always racing your fastest horse you will eliminate a minimum of 2 horses per round (as usual), however, instead of having to do 7 races since you don't know which horse is the fastest, after the end you DO know which horse is the fastest (since you've raced your fastest one every time) reducing your race count by 1
edit: god damn worst case gives 8 races, but its possible to do it by 5? in best case (5-6 i'm still not 100% sure)
Kinda annoying me now lol because i was expecting a more elegant solution but let me crack with it for longer
|
On March 29 2011 20:29 Adeeler wrote:
Think outside the box and inside the box also for the wolf lake problem.
Know your variables. 1 human, 1 wolf.
Swim a little side to side and the wolf will run the entire distance around the lake again and again and tire itself out.
Then proceed in any direction. Remember the math solution doesn't help you if the lake is so small the wolf always catchs you; you want a solution that encompasses all possible lake sizes which the math only solves for large lakes considering the speed of a human swimming is.
WTF? I hope you don't need a job.
|
Ok all done, best cast scenario = 6
Otherwise 7 is a surefire way to do it
With the risky way, you are garuanteed 8, but can get 6
|
On March 29 2011 20:46 BrTarolg wrote:
The more im working on the horse problem the more i am sure that the solution is 6
Even in the very worst case scenario, by always racing your fastest horse you will eliminate a minimum of 2 horses per round (as usual), however, instead of having to do 7 races since you don't know which horse is the fastest, after the end you DO know which horse is the fastest (since you've raced your fastest one every time) reducing your race count by 1
edit: god damn worst case gives 8 races, but its possible to do it by 5? in best case (5-6 i'm still not 100% sure)
Kinda annoying me now lol because i was expecting a more elegant solution but let me crack with it for longer
But wouldn't you need to measure the time other horses finish relative to that chosen horse for that? If you can do that might as well do it in 5 races. If you're comparing distances it gets a bit icky because the horses don't run at constant speed.
|
On March 29 2011 21:22 TrainSamurai wrote:Show nested quote +On March 29 2011 20:46 BrTarolg wrote:
The more im working on the horse problem the more i am sure that the solution is 6
Even in the very worst case scenario, by always racing your fastest horse you will eliminate a minimum of 2 horses per round (as usual), however, instead of having to do 7 races since you don't know which horse is the fastest, after the end you DO know which horse is the fastest (since you've raced your fastest one every time) reducing your race count by 1
edit: god damn worst case gives 8 races, but its possible to do it by 5? in best case (5-6 i'm still not 100% sure)
Kinda annoying me now lol because i was expecting a more elegant solution but let me crack with it for longer But wouldn't you need to measure the time other horses finish relative to that chosen horse for that? If you can do that might as well do it in 5 races. If you're comparing distances it gets a bit icky because the horses don't run at constant speed.
Let me give an example
You run the first five horses, eliminate two
Run the fastest horse from the first five, and then any 4 other horses
If the fastest horse from the first five comes 2nd, you can eliminate both 2 horses from your normal 5 horse group, AND you can eliminate the slowest horse from the first group
If he comes third, you can eliminate TWO horses from the first group
And if he comes last, you can eliminate a total of 4 horses in a single race
If every single race you find out your fastest horse was too slow, then you essentially eliminate 2 horses in the first race, and then 4 horses every single race thereafter. After 6 races, you are thus left with 3 horses, which are your fastest three ^^
Edit:
If you take a more complicated example, first five horses (a1-5), lose a4 a5
Now race A1 b1-4, and b1 comes first, a1 comes second
eliminate a3 and b3 b4
Now if you race B1 and C1-4, if C1 wins and B1 comes second, you can eliminate C3 C4 (as usual), but you can also eliminate A2 (since C1>B1>A1>A2)
Thus even with a second place, you can keep on eliminating larger number of horses given a non-worst case scenario
|
Is it true that some of these firms test you on the raw speed of your mental arithmetic?
On March 29 2011 19:23 paper wrote:![[image loading]](http://i.imgur.com/GAUuR.png) Columns are groups of horses in fives. They are conveniently sorted from fastest to slowest from the top left to the bottom right because... The first five races give you the top runners from each group. Throw the top runners from each group in a sixth race. You now have your guaranteed fastest horse at the most top left position. The seventh race has the leftover five horses marked by the orange circles (excluding the fastest horse at the upper left corner). The two winners are the remainder of your three fastest horses. This is just a matter of following the "circles" (when prioritizing going right over going down). That's just how I see it though ;p
I don't see how it follows from the first 6 races that (say) the 4th fastest horse in the column with the fastest horse is faster than the 4th fastest horse in any other column. What if, for example, the slowest horse and the fastest horse start off in the same column? It seems like 16 of those inequality signs are gratuitous.
Here's another way to think about it. If there's 3 horses faster than you, then you can't be in the top 3. After the first 6 races, there's only 5 horses left (besides the fastest) that aren't separated from the fastest horse by a 'chain' of length 3 or more
It might not the best method though.
|
I don't get the math in some of these. with the wolf, I think it makes more sense to wait for night and swim underwater to sneak away from him. These questions are coming from a humanities guy though.
Edit: I can't read 
|
Man, that gives me a headache. I mean, it's right per induction and makes perfect sense if you think about it mathematically (and logical), but it's still weird (and mind-blowing) that a not at all new information causes such a chain reaction.
|
I love questions like this, keep them coming.
|
On March 29 2011 17:54 DTK-m2 wrote:
2.) 30 strings. Two parallel rows of 30 holes. Each of the 30 strings goes through one of the 30 holes in the first row, and then one of the 30 holes in the second row. What is the expected number of crossovers, where one string overlaps the other?
This is pretty cool. As stated it's still ambiguous though - do you mean to say that exactly one string goes through every hole? Or can more than one go through the holes... I'll assume the former.
If you're matching up one left hole with one right hole 30 times, we're looking at a random element of S_30, the symmetric group on 30 objects. A configuration of the 30 strings is just a permutation s on {1,2,...,29,30}. That is, number the holes on each side from 1 to 30, and when you put all the strings on, for each n from 1-30, let s(n) be number at the right end of the string which starts at n at the left end. We want to know how many strings cross other strings. When do those crossovers happen? Well, whenever we have some pair of holes n and m with n<m and s(n)>s(m). In math-land these are called inversions. The number of inversions (i.e. the number of pairs in the list {s(1),s(2),...,s(29),s(30)} which are out of order) is the same as the number of times you'd have to interchange consecutive elements to get everything back to the correct order (i.e. the number of times you'd have to swap right endpoints of adjacent strings to get all the strings going straight across). The minimum number of inversions is obviously 0, corresponding to the identity permutation where every string goes straight across, and the maximum number of inversions obviously happens when every pair is out of order -- that is, s(1)=30, s(2)=29,... s(30)=1. Visually, this is when every string crosses every other and it makes a giant X. How many inversions is that? Well, if every string crosses every other we have one inversion for each possible pair of strings, which is (30 choose 2)=(30*29)/2=435.
The neat bit is that if you take any permutation and reverse the order (not the inverse element, I mean lexicographically reverse it), you get a permutation where all the incorrectly ordered pairs are correctly ordered and vice versa. So in our case, if s={s(1),s(2),...,s(30)} has k inversions, then defining s' to be the permutation {s(30),s(29),...,s(1)}, s' has exactly 435-k inversions.
But then if every permutation with k inversions has a corresponding permutation with 435-k inversions, a moment's thought tells us that *on average*, there will be 435/2 = 217.5 inversions, and that's your expected number of crossovers.
Notice that along the way we've actually proven the much more general fact that if you do this with N holes on each side and N strings, your expected number of crossovers is exactly (n choose 2)/2, which is n(n-1)/4.
P.S.: Despite being the language of group theory, this is reasonably intuitive stuff. Which by no means means it's easy, I just mean that I have no idea if this is the solution economics firms would expect. I'm a grad student doing pure math, and have no clue what goes on in the world of finance and applied math and what sorts of things people know and don't know.
|
Gah! Hit quote instead of edit...
|
1) run them all at the same time, 5 per lane.
|
P.S.: Despite being the language of group theory, this is reasonably intuitive stuff. Which by no means means it's easy, I just mean that I have no idea if this is the solution economics firms would expect. I'm a grad student doing pure math, and have no clue what goes on in the world of finance and applied math and what sorts of things people know and don't know.
You confused the hell out of me good sir. I understand what you did, sort of, but it boggles my mind. I've taken up to Calculus 3 and I could not come up with that answer on my own in an interview. It would have taken me at least a 30 minutes to figure it out. I'm doubting a firm would actually ask this question though. I'm looking at my College's Finance major requirements and only up to Calculus 1 is required. How any student with just some basic knowledge of Calculus is supposed to figure that out is beyond me.
|
On March 29 2011 23:26 Joementum wrote:Show nested quote +
P.S.: Despite being the language of group theory, this is reasonably intuitive stuff. Which by no means means it's easy, I just mean that I have no idea if this is the solution economics firms would expect. I'm a grad student doing pure math, and have no clue what goes on in the world of finance and applied math and what sorts of things people know and don't know.
You confused the hell out of me good sir. I understand what you did, sort of, but it boggles my mind. I've taken up to Calculus 3 and I could not come up with that answer on my own in an interview. It would have taken me at least a 30 minutes to figure it out. I'm doubting a firm would actually ask this question though. I'm looking at my College's Finance major requirements and only up to Calculus 1 is required. How any student with just some basic knowledge of Calculus is supposed to figure that out is beyond me.
they dont except a formal proof like he did, just that you can think yourself through to the soultion, and this is for the best of the best finance firms, some increadibly smart people work for these firms
|
On March 29 2011 18:35 eluv wrote:
5) There are 100 people in separate rooms. They can talk as much as they want until they "begin." Once they begin, they are called one at a time, in no particular order, into another room. In this room is only a light switch that turns on and off a lightbulb in the room. Noone can see the lightbulb unless they are in the room, and the only thing you can do in the room is check the lightbulb, turn it on, or turn it off. How do the people know when all 100 have been called? (You can be called more than once before everyone else has gone once).
Say there are 100 people, name them p_1, p_2, ... p_100.
Let p_1 be the tallier.
When p_1 enters the room, he must leave the light off when he leaves.
When p_i, for i = 2,3 ... 100 enters the room, he must leave the light on, if and only if he has not turned it on yet, and it is off when he has entered.
When p_1 turns the light off 99 times, he can assume all 100 have been called.
|
United States10328 Posts
On March 29 2011 22:59 Iranon wrote:Show nested quote +On March 29 2011 17:54 DTK-m2 wrote:
2.) 30 strings. Two parallel rows of 30 holes. Each of the 30 strings goes through one of the 30 holes in the first row, and then one of the 30 holes in the second row. What is the expected number of crossovers, where one string overlaps the other? This is pretty cool. As stated it's still ambiguous though - do you mean to say that exactly one string goes through every hole? Or can more than one go through the holes... I'll assume the former. If you're matching up one left hole with one right hole 30 times, we're looking at a random element of S_30, the symmetric group on 30 objects. A configuration of the 30 strings is just a permutation s on {1,2,...,29,30}. That is, number the holes on each side from 1 to 30, and when you put all the strings on, for each n from 1-30, let s(n) be number at the right end of the string which starts at n at the left end. We want to know how many strings cross other strings. When do those crossovers happen? Well, whenever we have some pair of holes n and m with n s(m). In math-land these are called inversions. The number of inversions (i.e. the number of pairs in the list {s(1),s(2),...,s(29),s(30)} which are out of order) is the same as the number of times you'd have to interchange consecutive elements to get everything back to the correct order (i.e. the number of times you'd have to swap right endpoints of adjacent strings to get all the strings going straight across). The minimum number of inversions is obviously 0, corresponding to the identity permutation where every string goes straight across, and the maximum number of inversions obviously happens when every pair is out of order -- that is, s(1)=30, s(2)=29,... s(30)=1. Visually, this is when every string crosses every other and it makes a giant X. How many inversions is that? Well, if every string crosses every other we have one inversion for each possible pair of strings, which is (30 choose 2)=(30*29)/2=435.
The neat bit is that if you take any permutation and reverse the order (not the inverse element, I mean lexicographically reverse it), you get a permutation where all the incorrectly ordered pairs are correctly ordered and vice versa. So in our case, if s={s(1),s(2),...,s(30)} has k inversions, then defining s' to be the permutation {s(30),s(29),...,s(1)}, s' has exactly 435-k inversions.
But then if every permutation with k inversions has a corresponding permutation with 435-k inversions, a moment's thought tells us that *on average*, there will be 435/2 = 217.5 inversions, and that's your expected number of crossovers.
Notice that along the way we've actually proven the much more general fact that if you do this with N holes on each side and N strings, your expected number of crossovers is exactly (n choose 2)/2, which is n(n-1)/4.
P.S.: Despite being the language of group theory, this is reasonably intuitive stuff. Which by no means means it's easy, I just mean that I have no idea if this is the solution economics firms would expect. I'm a grad student doing pure math, and have no clue what goes on in the world of finance and applied math and what sorts of things people know and don't know.
I tried some sort of silly induction approach, but then my friend owned me. The probability that two strings intersect given arbitrary starting positions is 1/2: for each crossing, there corresponds exactly one uncrossing (untwist the strings). There are nC2 ways of picking two starting positions. So by linearity of expectation, the total expected value is nC2/2 = n(n-1)/4. (This might be clearer if you just count the number of cross/uncrossings for each pair.)
|
7) There are N cars travelling along an infinitely long one-lane highway. No two cars travel at the same speed. When a car is travelling at a speed less than the car behind it, it forms a jam. How many jams are expected to be on this highway, in terms of n?
+ Show Spoiler [Hint] +Model a set from {1,...n} where a higher number => higher speed. Permutations
|
United States10328 Posts
On March 30 2011 00:40 Oracle wrote:7) There are N cars travelling along an infinitely long one-lane highway. No two cars travel at the same speed. When a car is travelling at a speed less than the car behind it, it forms a jam. How many jams are expected to be on this highway, in terms of n? + Show Spoiler [Hint] +Model a set from {1,...n} where a higher number => higher speed. Permutations
if n_a < n_{a+2} there's no ja
correct? only if n_a < n_{a+1}? and jams don't cause other jams? because then expected value works again: for each pair of adjacent cars, 1/2 probability of jam. n-1 pairs of cars, so (n-1)/2 jams are expected.
|
On March 30 2011 00:50 ]343[ wrote:Show nested quote +On March 30 2011 00:40 Oracle wrote:7) There are N cars travelling along an infinitely long one-lane highway. No two cars travel at the same speed. When a car is travelling at a speed less than the car behind it, it forms a jam. How many jams are expected to be on this highway, in terms of n? + Show Spoiler [Hint] +Model a set from {1,...n} where a higher number => higher speed. Permutations if n_a < n_{a+2} there's no ja correct? only if n_a < n_{a+1}? and jams don't cause other jams? because then expected value works again: for each pair of adjacent cars, 1/2 probability of jam. n-1 pairs of cars, so (n-1)/2 jams are expected.
Consider the set {6, 4, 5, 7, 2}
4,5 form a jam, but also 4,5,7 forms a jam. So yes, jams may cause other jams.
However, jams are counted contiguously, {4,5} would be not regarded as a different jam than {4, 5, 7}
|
United States10328 Posts
On March 30 2011 01:00 Oracle wrote:Show nested quote +On March 30 2011 00:50 ]343[ wrote:On March 30 2011 00:40 Oracle wrote:7) There are N cars travelling along an infinitely long one-lane highway. No two cars travel at the same speed. When a car is travelling at a speed less than the car behind it, it forms a jam. How many jams are expected to be on this highway, in terms of n? + Show Spoiler [Hint] +Model a set from {1,...n} where a higher number => higher speed. Permutations if n_a < n_{a+2} there's no ja correct? only if n_a < n_{a+1}? and jams don't cause other jams? because then expected value works again: for each pair of adjacent cars, 1/2 probability of jam. n-1 pairs of cars, so (n-1)/2 jams are expected. Consider the set {6, 4, 5, 3, 2} 4,5 form a jam, but also 4,5,3 forms a jam. So yes, jams may cause other jams. However, jams are coutned contiguously, {4,5} would be not regarded as a different jam than {4, 5, 3}
did you mean to say (4,5) is not a jam? or are numbers to the left the cars in front... or are your numbers inversely related to the speed. ok I'm confused lol.
let a number represent speed and coordinates with higher index be in front (as if cars traveled right).
so 5 4 3 2 1 is how many jams? 1? how about 2 3 1? does the 2 count as part of the same jam, since the 3-car is slowed to 1?
|
I wish all Jane Street cared about was math haha, got to final round and Tim told me I was too quiet and mumbled too much =[
|
On March 30 2011 01:19 ]343[ wrote:Show nested quote +On March 30 2011 01:00 Oracle wrote:On March 30 2011 00:50 ]343[ wrote:On March 30 2011 00:40 Oracle wrote:7) There are N cars travelling along an infinitely long one-lane highway. No two cars travel at the same speed. When a car is travelling at a speed less than the car behind it, it forms a jam. How many jams are expected to be on this highway, in terms of n? + Show Spoiler [Hint] +Model a set from {1,...n} where a higher number => higher speed. Permutations if n_a < n_{a+2} there's no ja correct? only if n_a < n_{a+1}? and jams don't cause other jams? because then expected value works again: for each pair of adjacent cars, 1/2 probability of jam. n-1 pairs of cars, so (n-1)/2 jams are expected. Consider the set {6, 4, 5, 3, 2} 4,5 form a jam, but also 4,5,3 forms a jam. So yes, jams may cause other jams. However, jams are coutned contiguously, {4,5} would be not regarded as a different jam than {4, 5, 3} did you mean to say (4,5) is not a jam? or are numbers to the left the cars in front... or are your numbers inversely related to the speed. ok I'm confused lol. let a number represent speed and coordinates with higher index be in front (as if cars traveled right). so 5 4 3 2 1 is how many jams? 1? how about 2 3 1? does the 2 count as part of the same jam, since the 3-car is slowed to 1?
Sorry i made an error in my post, i updated it.
5 4 3 2 1 is zero jams, since 5 travels faster than 4, faster than 3, etc. so none would be bottlenecked by another car
2 3 1 would be 1 jam, since 3 is bottlenecked by 2, but 1 cannot catch up to 2 to be bottlenecked.
(i am reading the cars travelling left, not right, thats where u may be confused)
1 2 3 4 5 would be a single jam
1 3 2 would be a single jam
+ Show Spoiler [Hint] +my answer requires calculus/finite series
|
8) Two mathematicians who haven't seen each other in 14 years are talking.
A: "I have three daughters now. The product of their ages is 72. and the sum of their ages is equal to the amount of years we have known each other.
B: "I still don't know how old they are"
A: "My youngest daughter just started to play the piano"
B: "Oh, my youngest is the same age!"
How old are person A's daughters?
+ Show Spoiler [hint] +
|
United States10328 Posts
On March 30 2011 02:15 Oracle wrote:8) Two mathematicians who haven't seen each other in 15 years are talking. A: "I have three daughters now. The product of their ages is 72. and the sum of their ages is equal to the amount of years we have known each other. B: "I still don't know how old they are" A: "My youngest daughter just started to play the piano" B: "Oh, my youngest is the same age!" How old are person A's daughters? + Show Spoiler [hint] +
6*6*2 = 3*3*8 = 72, and both have sum 14; they're the only triples with product 72 that have the same sum (hence ambiguity). but since he has a distinct youngest daughter, she must be 2. ... except they can't have known each other for less than 15 years =.= but I'll assume that was extraneous information that happens to be false ;P
|
On March 30 2011 01:26 raiame wrote:
I wish all Jane Street cared about was math haha, got to final round and Tim told me I was too quiet and mumbled too much =[
You applied to Jane Street? How hard would you say the math was?
|
On March 30 2011 02:15 Oracle wrote:8) Two mathematicians who haven't seen each other in 15 years are talking. A: "I have three daughters now. The product of their ages is 72. and the sum of their ages is equal to the amount of years we have known each other. B: "I still don't know how old they are" A: "My youngest daughter just started to play the piano" B: "Oh, my youngest is the same age!" How old are person A's daughters? + Show Spoiler [hint] +
Did some Googling. Its an interesting problem.
+ Show Spoiler +The only knowledge you initially seem to have to go on is that the product of their ages is 72. The second clue seems meaningless. However, the final clue tells you in that one of the numbers is strictly smaller than the other two (which could just as easily be the same number as not). Since 72 isn't a perfect cube, then there's a limited number of answers it could be.
a * b * c = 72
a + b + c = D
Possible values are
==============
a = 24, b = 3, c = 1, D = 28
a = 18, b = 4, c = 1, D = 23
a = 12, b = 6, c = 1, D = 19
a = 12, b = 3, c = 2, D = 17
a = 9, b = 8, c = 1, D = 18
a = 9, b = 4, c = 2, D = 15
a = 8, b = 3, c = 3, D = 14
a = 6, b = 6, c = 2, D = 14
a = 6, b = 4, c = 3, D = 13
Because of the first clue, a must be less than 15, and because of the second clue, D must be greater than 15, which leaves us with:
a = 12, b = 6, c = 1, D = 19
a = 12, b = 3, c = 2, D = 17
a = 9, b = 8, c = 1, D = 18
So, the youngest daughter is either 1 or 2, but since a 1-year old is mostly still crawling around the floor, rather than playing piano, her age must be 2, which leaves the other daughter's ages as 3 and 12.
Edit:
+ Show Spoiler +Although the poster above, ]343[, brings up a good point. Mathematician B would know the value of D, but the only reason to ask why they didn't know the answer after being given the second clue would be if there was ambiguity in the results, and that only occurs where D is equal to 14, so the only two outcomes are:
a = 6, b = 6, c = 2, D = 14
a = 8, b = 3, c = 3, D = 14
Since there's a youngest, the answer has to be 6, 6, 2.
It seems like these kinds of interview questions don't really have a purpose. If someone asked me about this problem in an interview now, I'd be able to solve it in 20 seconds. If they asked me 20 minutes ago, I'd just stumble around for 10 minutes and give up. All they reveal is how much brushing up someone did prior to the interview.
|
On March 30 2011 02:45 ]343[ wrote:Show nested quote +On March 30 2011 02:15 Oracle wrote:8) Two mathematicians who haven't seen each other in 15 years are talking. A: "I have three daughters now. The product of their ages is 72. and the sum of their ages is equal to the amount of years we have known each other. B: "I still don't know how old they are" A: "My youngest daughter just started to play the piano" B: "Oh, my youngest is the same age!" How old are person A's daughters? + Show Spoiler [hint] + 6*6*2 = 3*3*8 = 72, and both have sum 14; they're the only triples with product 72 that have the same sum (hence ambiguity). but since he has a distinct youngest daughter, she must be 2. ... except they can't have known each other for less than 15 years =.= but I'll assume that was extraneous information that happens to be false ;P
Sorry typo, my fault, i dont really proofread at work
|
On March 30 2011 02:46 DTK-m2 wrote:Show nested quote +On March 30 2011 01:26 raiame wrote:
I wish all Jane Street cared about was math haha, got to final round and Tim told me I was too quiet and mumbled too much =[ You applied to Jane Street? How hard would you say the math was?
Early rounds would be problems similar to those given here.
Later rounds math wasn't easy enough that you could solve and you would just have to guess and make markets/confidence intervals and give thought processes/reasoning.
Final round was mostly on decision making based on mathematical questions.
|
On March 29 2011 17:54 DTK-m2 wrote:
I made AIME in high school and got an 11
...what I thought you got a 6. Was this in a different year?
Darn I can't stop thinking about the "jams" problem.
Anyway, progress so far:
+ Show Spoiler +This is equivalent to the number of increasing subparts (i'm sure there's a more technical term) of a permutation of length at least 2. It's probably easier to include all increasing subparts and then subtract the expected number of increasing subparts of length 1. When do those occur? when a number has a higher number before it and a lower one after it (or just the relevant one if it's the first or last). Thus there are an expected 2/2+(n-2)/4=(n+2)/4 increasing subparts of length 1. Now to count the total number of increasing subparts. Since my combo is awful I will attempt to biject and probably fail, but interesting problem!
BTW, does LaTEX work on TL?
|
United States10328 Posts
On March 31 2011 10:49 bpgbcg wrote:Show nested quote +On March 29 2011 17:54 DTK-m2 wrote:
I made AIME in high school and got an 11 ...what I thought you got a 6. Was this in a different year? Darn I can't stop thinking about the "jams" problem. Anyway, progress so far: + Show Spoiler +This is equivalent to the number of increasing subparts (i'm sure there's a more technical term) of a permutation of length at least 2. It's probably easier to include all increasing subparts and then subtract the expected number of increasing subparts of length 1. When do those occur? when a number has a higher number before it and a lower one after it (or just the relevant one if it's the first or last). Thus there are an expected 2/2+(n-2)/4=(n+2)/4 increasing subparts of length 1. Now to count the total number of increasing subparts. Since my combo is awful I will attempt to biject and probably fail, but interesting problem! BTW, does LaTEX work on TL?
lolsup I've seen your username on AoPS. anyway LaTeX doesn't work, just BBCode. (why would LaTeX work on a non-math forum...?) though if you want, I'm sure you could use the TeXer and just include the images lol.
also, I'm not sure what you're talking about in the "subparts" at all. please elaborate.
|
On March 31 2011 10:49 bpgbcg wrote:Show nested quote +On March 29 2011 17:54 DTK-m2 wrote:
I made AIME in high school and got an 11 ...what I thought you got a 6. Was this in a different year? Darn I can't stop thinking about the "jams" problem. Anyway, progress so far: + Show Spoiler +This is equivalent to the number of increasing subparts (i'm sure there's a more technical term) of a permutation of length at least 2. It's probably easier to include all increasing subparts and then subtract the expected number of increasing subparts of length 1. When do those occur? when a number has a higher number before it and a lower one after it (or just the relevant one if it's the first or last). Thus there are an expected 2/2+(n-2)/4=(n+2)/4 increasing subparts of length 1. Now to count the total number of increasing subparts. Since my combo is awful I will attempt to biject and probably fail, but interesting problem! BTW, does LaTEX work on TL?
Ah fine, you caught me. Hi Ben. :D
I got a six freshman year, and senior year I ALMOST got an 11. Like, I would have had it if I knew how to do addition. And simple multiplication. Or read English. My actual score was a 7? or an 8? One of those 2.
|
United States10328 Posts
On March 31 2011 12:29 DTK-m2 wrote:Show nested quote +On March 31 2011 10:49 bpgbcg wrote:On March 29 2011 17:54 DTK-m2 wrote:
I made AIME in high school and got an 11 ...what I thought you got a 6. Was this in a different year? Darn I can't stop thinking about the "jams" problem. Anyway, progress so far: + Show Spoiler +This is equivalent to the number of increasing subparts (i'm sure there's a more technical term) of a permutation of length at least 2. It's probably easier to include all increasing subparts and then subtract the expected number of increasing subparts of length 1. When do those occur? when a number has a higher number before it and a lower one after it (or just the relevant one if it's the first or last). Thus there are an expected 2/2+(n-2)/4=(n+2)/4 increasing subparts of length 1. Now to count the total number of increasing subparts. Since my combo is awful I will attempt to biject and probably fail, but interesting problem! BTW, does LaTEX work on TL? Ah fine, you caught me. Hi Ben. :D I got a six freshman year, and senior year I ALMOST got an 11. Like, I would have had it if I knew how to do addition. And simple multiplication. Or read English. My actual score was a 7? or an 8? One of those 2.
oh wait. he's... ben from... GDS?! oh that would explain the 14  loooool ok it all makes sense now!
|
On March 29 2011 21:40 Wonders wrote:
Is it true that some of these firms test you on the raw speed of your mental arithmetic?
It's a different kind of firm. Jane Street is more like a hedge fund as far as I know, while the speed math tests are typically in market making / arbitrage firms. In Europe/ Asia some examples of such firms are Optiver, All Options, Tibra... great career if you can pass the tests. In the US I don't know them as well, there are a lot of these firms in Chicago but for some reason they don't seem to have much presence internationally as far as I can tell.
|
My start of a solution was completely unhelpful. Here is an actual one.
So + Show Spoiler + If higher number=higher speed, each jam is started by a number for which the numbers on either side are both higher than it. (If the one on the left was lower it would not be the beginning of a jam, if the one on the right was lower it would not cause a jam at all.) So what's the probability for this to happen for any given number? For the n-2 middle numbers, the probability that out of any 3 adjacent ones the middle is the smallest is clearly 1/3. However, for the one on the right side it cannot start a jam, whereas for the one on the left the probability is 1/2. Thus we have (n-2)/3+1/2=(2n-1)/6.
Also ]343[ do I know you?
|
Sorry, that's wrong.
The arithmetic solution which I got was
+ Show Spoiler +1 + 1/2 + ... + 1/(n-1) + 1/n
I didn't give the explanation but sometimes it helps to know the answer and work backwards.
|
Darn I fail misread the question.
+ Show Spoiler +If the slowest car is the kth car from the back it creates a jam behind it. In addition if f(n) is the number of expected jams, there are f(n-k) expected more jams in front of the slowest car. Since each of these is equally probable, we have f(n)=(f(n-1)+f(n-2)+...+f(1))/n+1. Thus nf(n)=f(n-1)+...+f(1)+n. Thus nf(n)-(n-1)f(n-1)=f(n-1)+1, so f(n)=f(n-1)+1/n. Induction trivially yields f(n)=H_n.
|
Do you assume that single car forms a jam after all? For n=1 your solution tells that there will be 1 jam...
With that simplification I can confirm that answer. Here is how i got it:
+ Show Spoiler +
X_i = 1 if i-th slowest car is blocked by a jam, 0 otherwise
Y - number of jams (including 'single-car jams')
The following holds (P denotes probability):
P(X_i=1) = 1 - 1/i
explanation: look at subset {1,2,...,i-1} of i slowest cars. The chance that i-th
car has no slower car anywhere in front equals to the chance that i is at the first position of i-permutation, which is 1/i.
Observe that (E denotes expected value):
Y = N - (sum of EX_i)
Then the answer to the simplified problem is:
EY = N - (sum of EX_i) = N - (N - 1 - 1/2 - ... - 1/N) = 1+1/2+...+1/N = H_N
Would be interesting to know the answer for the original problem though 
|
Straight outta Johto18973 Posts
Generally with these firms they want to see how good your analytical skills are. Getting the correct answer is always good, especially if you know the answer beforehand. However, what's more important is that you show you can think through things logically and critically. That should get you to the correct answer.
As for the standard of math. If you want to get into finance, having done further mathematics at secondary school is a must. Having done mathematics or quantitative subjects at university is recommended. While you don't necessarily have to have done finance at university, a lack of mathematical background will set you back. This is especially important for the more quantitative-finance orientated positions, such as say Financial and Audit Consulting at one of the Big Four.
Different companies will also ask different styles of questions. You'd probably want to do some research or talk to previous applicants about what the company is looking for. Different departments in different countries will also have different standards on what they want because the recruiters all have their own preferences so check beforehand if you can. Ultimately, trying to read up on every brainteaser in existence probably won't be a great strategy as there's too many to learn. You'll probably have to do psychometric testing as well and you don't want to perform poorly on them. Those matter a lot because if you don't make the cut, they just reject you then and there.
I'd also recommend knowing how to do mental math fast. For example, knowing the tricks to multiplying any two digit number by 11, or converting decimals into fractions.
As for the questions themselves:
Question 1:
+ Show Spoiler +The answer is 7.
Divide your horses into 5 groups of 5. Race each group of 5. Let us call each group A, B, C, D, E with and the rank the horses 1, 2, 3, 4, 5. We then have:
A1, A2, A3, A4, A5
B1, B2, B3, B4, B5
C1, C2, C3, C4, C5
D1, D2, D3, D4, D5
E1, E2, E3, E4, E5
Now we race A1, B1, C1, D1, E1. Let's just say that the final result has A being the fastest, B coming second, C third, etc. Since these are just labels, you can relabel them with something else if you want.
We can eliminate everything in group D and E for obvious reasons. We also eliminate C2 to C5 as we can always form a group of 3 faster horses (e.g. A1, B1, C1). The same logic allows us to eliminate B3 to B5 and A4 and A5.
We have A1, A2, A3, B1, B2, C1 left. We know A1 is the fastest horse of them all. So race the remaining 5 and choose the two fastest from the rest.
Question 2:
+ Show Spoiler +I don't actually understand this question. Is each string only allowed through 1 hole?
Question 3:
+ Show Spoiler +The fact they don't burn uniformly doesn't matter.
Light string 1 at both ends at the same time and light string 2 at one end. String 1 will fully burn in 30 minutes. String 2 will be half burnt. When String 1 fully burns, light the non-lit end of string 2. String 2 will now burn for 15 more minutes on top of the 30 min it has already burnt.
Question 4:
+ Show Spoiler +The answer on Page 1 was correct.
Question 5:
+ Show Spoiler +The solution on Page 2 works, but you probably won't get out of jail until the universe ends because the amount of time it would take for everyone to be randomly selected and have visited the room and then have one person go back would take far too long. I believe the most elegant solution would be this one which also covers every possible variation of the problem.
Question 6:
+ Show Spoiler +This a pretty well known question with many explanatory solutions so I won't type one up here.
|
It's pretty simple actually. Just swim in a very tight circle around the center of the lake for 15 minutes. Then swim to the edge and escape. The wolf will have run around the lake so many times it will be dead of exhaustion.
|
|
|
|
|
|
EPT
