Quant puzzles, solved step by step
- Puzzles
- 100
- Traced to a firm
- 71
- Topics
- 12
- Hard
- 30
003Speed round, ninety seconds: you draw three cards from a well-shuffled 52-card deck without replacement. What is the probability that all three are of different suits?Quant tradingProp trading firms
Try it first
Closest answer, fast.
Show the worked solution
About 39.8%. The first card can be anything. The second must come from one of the three other suits: 39 of the 51 cards left. The third must avoid both suits already seen: 26 of the 50 left. Multiply: 39/51 x 26/50 = 1,014/2,550, just under 40%. Drawing with replacement would give 3/4 x 1/2 = 37.5%.
Why does the first card cost nothing?
Picture three guests arriving at a party with four dress colours in the wardrobe, and you want no two to match. The first guest cannot clash with anyone. A condition about the cards differing only bites from the second card on, so the first card contributes a factor of 1 and you start counting from card two. Candidates who write 13/52 for the first card have fixed a particular suit and then have to multiply by the number of suit orders to recover, which is where the slips happen.
The first card is free, the second must avoid one used suit with 39 of 51 cards still good, and the third must avoid two with 26 of 50 still good, so three different suits happen with probability 39.8%. How do you check it a second way in the time?
Count unordered hands. Choose which three suits appear, 4 ways, then one card from each, 13 cubed, and divide by all three-card hands, 52 choose 3. That is 4 x 2,197 = 8,788 over 22,100, which is the same 0.3976. In a speed round you do not have time for both, but knowing the counting route exists lets you sanity-check the product: 0.765 x 0.52 is a little under 0.40.
The relationship39/51 cards of a new suit among those left after one draw 26/50 cards of a third suit after two draws \binom{52}{3} the number of possible three-card hands What it says in wordsSequential dodging and direct counting give the same 39.8%.What is a speed round actually testing?
Thirty questions in forty-five minutes cannot all be worked in full. The skill being tested is choosing the shortest correct route and estimating the product well enough to pick from the options. Here, 39/51 is about 0.76 and 26/50 is 0.52; 0.76 x 0.52 is about 0.40, which eliminates every other option before you finish the exact fraction.
Where candidates lose it
The fast wrong answer is 37.5%, from treating the draws as if cards go back in the deck. It feels close enough, and in a multiple choice round it sits right next to the correct option on purpose.
The other slip is starting with 13/52 for the first card, which silently fixes that card's suit. You then need to multiply by 4 for the suit choice, and under time pressure most people forget.
What the interviewer asks next
- What is the probability that four cards are all of different suits?
- What is the probability that three cards share a suit?
- Draw until you have seen all four suits. What is the expected number of cards?
055In how many ways can three positive integers, in order, sum to 10? To 11? Give the general formula for any total n of at least 3.Old Mission CapitalNew York · 2018
Try it first
How many ordered triples of positive integers sum to 10?
Show the worked solution
36 for 10, 45 for 11, and (n - 1)(n - 2)/2 in general. Write n as a row of n stars. Splitting it into three positive parts means placing two bars in two different gaps among the n - 1 gaps between stars. Each choice gives exactly one ordered triple, so the count is n - 1 choose 2: 9 choose 2 = 36 and 10 choose 2 = 45.
Why turn the sum into a row of stars?
Think of ten sweets in a line to be shared among three children in order, each getting at least one. You do not need to decide amounts; you only need to decide where to cut the line. Every ordered split of n into three positive parts is exactly one choice of two cut points among the n - 1 gaps between items, and every choice of two gaps gives a valid split. That one-to-one match is the whole argument, and it is what the interviewer wants to hear you state.
Ten stars have nine gaps between them; putting bars in two different gaps, here gaps 3 and 7, splits the stars into 3, 4 and 3, so the ordered triples summing to 10 number 9 choose 2, which is 36, and those summing to 11 number 45. What if the interviewer meant something slightly different?
Ask two quick questions before you answer: are zeros allowed, and does order matter. The word numbers hides three different questions, and each has a different count. If zeros are allowed, add one to each part first so they become positive and sum to n + 3: for 10 that is 12 choose 2 = 66. If order does not matter, the count for 10 drops to 8 unordered triples, and for 11 to 10, which you would list rather than compute. Asking which one is wanted takes five seconds and is part of the answer.
The relationshipn - 1 the number of gaps between n stars 2 the number of bars needed to make three parts What it says in wordsChoose two of the gaps between the stars; each choice is one ordered triple.How do you check 36 without the formula?
Fix the first number and count the rest. If the first part is a, the other two must sum to 10 - a, which can be done in 9 - a ordered ways. For a from 1 to 8 that is 8 + 7 + ... + 1 = 36. The counts for each total are the triangular numbers 1, 3, 6, 10 and so on, which is the same formula read another way.
Where candidates lose it
The fast wrong answer comes from listing unordered triples such as 1, 1, 8 and 2, 3, 5, getting 8, and not noticing the question counts order. The opposite slip is counting zeros and getting 66.
Both are avoided by one clarifying question at the start. Then give the stars and bars picture in a sentence, because the interviewer's next question is usually four or five parts.
What the interviewer asks next
- How many ways can four positive integers sum to 10?
- How many ordered triples of non-negative integers sum to 10?
- How many ordered triples of positive integers sum to 10 with every part at most 5?
Asked at Old Mission Capital, Finance, New York, 2018 (Wall Street Oasis):
In how many ways can you have three numbers that sum to 10? What about 11?
092You climb a staircase of 10 steps, taking either one step or two steps at a time. In how many different ways can you reach the top?Tower Research CapitalNew York · 2012
Try it first
Pick the number of ways.
Show the worked solution
89 ways. Split by the last move: you arrive at step 10 with a single from step 9 or a double from step 8, so ways(10) = ways(9) + ways(8). With 1 way to reach step 1 and 2 ways to reach step 2, the counts run 1, 2, 3, 5, 8, 13, 21, 34, 55, 89: the Fibonacci numbers, with 89 at the top.
How do you count without listing every route?
Imagine a friend at the top of the stairs asks how you got there. There is one thing you can say for certain about your last move: it was either a single from step 9 or a double from step 8, and never both. Every route to step 10 is a route to step 9 followed by a single, or a route to step 8 followed by a double, so the count at step 10 is the sum of the counts at steps 9 and 8. The same holds at every step, which turns the puzzle into a running sum.
Writing the number of ways on each step, each step is the sum of the two below it, so the counts follow the Fibonacci sequence and step 10 collects 55 routes ending with a single and 34 ending with a double, 89 in all. The relationshipw(n) the number of ways to reach step n w(n-1) routes whose last move is a single step w(n-2) routes whose last move is a double step What it says in wordsSort every route by its last move; the two groups do not overlap and together cover everything.Can you check 89 a second way?
Count by how many double steps you take. With k doubles, you make 10 - 2k singles, so 10 - k moves in all, and you only have to choose which k of those moves are the doubles. Summing the binomial counts over k = 0 to 5 gives 1 + 9 + 28 + 35 + 15 + 1 = 89, the same answer by a completely different road. Saying a second check aloud is worth more than the answer itself in a first round, because it shows you do not trust a pattern you have not tested.
Double steps k Moves in total Ways to place the doubles 0 10 C(10, 0) = 1 1 9 C(9, 1) = 9 2 8 C(8, 2) = 28 3 7 C(7, 3) = 35 4 6 C(6, 4) = 15 5 5 C(5, 5) = 1 total 89 Counting routes by the number of double steps gives 89 again, which confirms the Fibonacci running sum. What does the interviewer usually ask next?
Two things. First, allow steps of one, two or three: the same last-move argument gives w(n) = w(n - 1) + w(n - 2) + w(n - 3), and the count for ten steps becomes 274. Second, the coding version. A recursive function that calls itself for n - 1 and n - 2 recomputes the same steps again and again: for 30 steps it makes 1,664,079 calls to return 1,346,269. Storing each step's count once, or just keeping the last two numbers in a loop, does the job in 30 additions. The counts grow by about 1.618, the golden ratio, per step, which is the limitation of any approach that lists routes rather than counting them.
Where candidates lose it
The fast wrong answer is 2^10 = 1,024, treating each of ten stairs as a binary choice. A double step consumes two stairs, so routes have different numbers of moves and the choices are not ten independent coin flips.
The second loss is an off-by-one in the starting values, which lands on 55 or 144. Write the first three steps out by hand: 1 way to step 1, 2 ways to step 2, 3 ways to step 3. Anchor the sequence there and the tenth term is 89.
What the interviewer asks next
- What if you can also take three steps at a time?
- How many ways are there if step 5 is broken and cannot be stood on?
- Write code that counts the ways for 1,000 steps without the recursion blowing up.
Asked at Tower Research Capital, Intern Interview -, New York, 2012 (Wall Street Oasis):
How many ways can you jump up stairs if you can only jump either 1 or 2 steps?
