Quant puzzles, solved step by step

2 to the power (n - 1) divided by n factorial, which is 16/120 = 2/15 for n = 5. One pass moves every number that is not carried rightwards exactly one place left. So the list ends sorted only if no number starts more than one place right of its final spot. Placing 1, then 2, then 3 and so on, each has two allowed spots and the largest takes the last one, giving 2 to the power (n - 1) orderings.

What does one pass actually do to each number?

Picture a queue at a ticket window where the tallest person seen so far keeps stepping back past anyone shorter. That person travels a long way to the right; everyone they pass shifts one step forward. In one pass, the running maximum is carried right until it meets something larger, and every number it passes moves exactly one place left. Nothing moves left by two in a single pass. That limit is the whole problem.

Which orderings survive, and how do you count them?

Because a number can shift left by one at most, the list sorts only if each number starts no more than one place right of its home. The converse also holds: when every number meets that condition, the pass carries each big number to exactly where it belongs. For five numbers, a brute-force check of all 120 orderings finds exactly the 16 that meet the condition, and all 16 sort.

Now count them without listing. Place the numbers in increasing order. The 1 may sit in position 1 or 2. The 2 may sit anywhere in positions 1 to 3, one of which the 1 already took: two choices. The same holds for 3 and 4: each has k + 1 allowed spots, k - 1 of them already used by smaller numbers, so two choices each. The 5 fills the one position left. That is 2 x 2 x 2 x 2 x 1 = 16.

Check small cases out loud: for n = 2 both orderings sort, 2 of 2; for n = 3 it is 4 of 6. The probability collapses fast, because n factorial outruns 2 to the power n: about 4.4% for n = 6 and 1.3% for n = 7.

8 cubes have 3 painted faces, 12 have 2, 6 have 1 and 1 has none; the chance the top face is painted is exactly 1/3. Corners carry three, edge middles two, face centres one, and the core none. Picking a random cube and rolling it picks a random small face out of 27 x 6 = 162. The painted ones are the big cube's surface, 6 x 9 = 54, so the probability is 54/162 = 1/3.

Where do the 8, 12, 6 and 1 come from?

Think of a Rubik's cube: its pieces are corners, edges and centres, plus a hidden core. A small cube's painted faces equal the number of outer walls it touches: a corner touches three, an edge middle two, a face centre one, the core none. A cube has 8 corners, 12 edges with one middle piece each, and 6 faces with one centre each. That accounts for 8 + 12 + 6 = 26 cubes; the 27th is the core.

Why is the roll probability exactly one third?

Do it the long way first: weight each cube type by its share of cubes and its share of painted faces. 8/27 x 3/6 + 12/27 x 2/6 + 6/27 x 1/6 + 1/27 x 0 = (24 + 24 + 6)/162 = 54/162. Then notice the shortcut: a random cube with a random face up is a uniform pick from all 162 small faces, and the painted small faces are exactly the big cube's surface, 6 x 9 = 54. That gives 1/3 without any case split, and it works for any size: an n x n x n cube gives 6n squared over 6n cubed, which is 1/n.

Interviewers use the second part to see whether you look for the structure before the arithmetic. Counting faces instead of cubes turns a four-case weighted average into one division. Say both routes: the case split proves you can count, the face count proves you can see.

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.

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.

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.

110 paths avoid the block, so the probability is 110/210 = 11/21, about 52.4%. All shortest paths use 6 rights and 4 ups in some order: C(10,4) = 210. Paths through (3,2) combine 10 ways in with 10 ways out, 100 in all. Subtract, and 110 survive.

How do you count all the shortest paths?

A shortest path is a string of 10 moves with exactly 6 rights and 4 ups, like a ten-letter word made of R and U. Choosing which 4 of the 10 slots are ups fixes the path completely, so there are C(10,4) = 210 shortest paths. That is the whole sample space, and every one of those strings is equally likely by the question's rule.

Why multiply for the paths through the blocked point?

Think of a trip from home to the office with a stop at a coffee shop. If there are 10 routes to the shop and 10 routes from the shop to the office, there are 10 x 10 = 100 full trips, because every first half pairs with every second half. Paths through (3,2) split the same way: C(5,2) = 10 in and C(5,2) = 10 out, so 100 of the 210 pass through the block. Subtract and 110 remain.

The grid method in the figure is the check, and it is also what you would code. Each point's count is the count from the left plus the count from below, because the last step into any point came from one of those two neighbours. Setting the block to zero removes every path through it automatically, and the same method handles several blocks, where the subtraction formula needs inclusion and exclusion.

Does the answer change if the walker flips a coin at each step?

Yes, and interviewers often ask this next. If the walker flips a fair coin for right or up at each step, any visit to (3,2) happens on move five, and a walker still able to get there has not yet touched the top or right edge, so all five of those moves were free coin flips. The chance of standing on (3,2) after five flips is C(5,2)/2^5 = 10/32 = 5/16, so the coin-flip walker avoids the block with probability 11/16, about 68.8%, well above 11/21. Choosing uniformly among complete paths is not the same as flipping coins: conditioning on the end point (6,4) pulls paths towards the diagonal that leads there, and (3,2) sits on it. Say which model the question means before you answer.

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.

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.

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.