Quant puzzles, solved step by step
- Puzzles
- 100
- Traced to a firm
- 71
- Topics
- 12
- Hard
- 30
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?
