Derivatives Foundation puzzles, solved step by step

7/18 of the circle, about 38.9%. A gap between neighbouring points stays blank only when it is longer than both gaps beside it. For large n the gaps behave like independent exponentials with the same mean, and the expected length of the longest of three is 1 + 1/2 + 1/3 = 11/6 times the mean. Any one of the three is longest a third of the time, so the blank share of length is (11/6)/3 = 11/18, and the coloured share is 1 minus that, 7/18.

Why is the question about gaps and not about points?

Think of houses along a ring road where each household paints the stretch of road to its nearest neighbour. A stretch of road gets paint from the house at either end, so to find the unpainted road you ask which stretches are chosen by neither house. A gap is blank exactly when it is longer than both of its neighbouring gaps, because then each of its end points has a closer neighbour on the other side. That turns the problem into a question about one gap and its two neighbours, which is small enough to solve.

Why 11/18 and not 1/3 for the blank share?

Each gap is the longest of its three with probability 1/3, by symmetry. But the question asks for length, not count, and the gaps that stay blank are the long ones. The blank share is the expected length of a gap that is the longest of three, divided by the mean gap, which for exponential gaps is (1 + 1/2 + 1/3)/3 = 11/18. Count and length give different answers because being blank is correlated with being long. That distinction is the whole difficulty of the question, and saying it out loud is most of the marks.

Where does the 1 + 1/2 + 1/3 come from, and what are you assuming?

Three exponential clocks run together. The first to ring takes an expected 1/3 of the mean; then two remain, memoryless, and the next takes 1/2; the last takes a full mean. Adding gives 11/6 for the longest. The assumption is that neighbouring gaps are independent, which is exact in the limit of many points and only approximate for small n, where the gaps must sum to 1. A quick simulation with 2,000 points gives a coloured share of 0.388, against 7/18 = 0.389. The exact answer for any n differs slightly and settles to 7/18 as n grows.

5/9, about 55.6%. Put A's arrival time across and B's up a 60 by 60 square; every pair of times is a point, all equally likely, so probability is area. They meet when the times are within 20 minutes, the band either side of the diagonal. They miss in two corner triangles, each with legs of 40 minutes and area 800 of 3,600, which is 2/9. So the meeting chance is 1 minus 4/9 = 5/9.

Why turn two arrival times into a square?

Throw a dart at a square board without aiming and the chance it lands in any patch is just that patch's share of the board. Two independent arrival times, each spread evenly over the hour, behave exactly like that dart: A's time picks a position across, B's time picks a position up. With two independent uniform times, every pair of arrivals is a point in a 60 by 60 square, equally likely anywhere in it, so a probability becomes an area you can see. The event they meet is the set of points where the two times differ by less than 20 minutes, a band hugging the diagonal.

Why is it easier to compute where they miss?

The band is an awkward six-sided shape; the regions outside it are two clean triangles. In the top-left triangle B arrives more than 20 minutes after A, so A has gone; in the bottom-right one, A is the late one. Each triangle has legs of 60 minus 20 = 40 minutes, so its area is 40 x 40 / 2 = 800 square minutes out of 3,600, which is 2/9, and the two together are 4/9. The clause about leaving at 2 pm changes nothing, because no one can arrive after 2 pm anyway; it only stops the question from looking ambiguous.

How does the answer move with the waiting time?

Not in a straight line, and that is a common follow-up. Doubling the wait from 10 to 20 minutes takes the meeting chance from about 31% to about 56%, not from one third to two thirds, because the miss region shrinks as a square. The table runs the formula for four waits. The trading version is two orders that must arrive within a latency window to match: halving the gap you can tolerate does more than halve the matches, and a picture of the square is the fastest way to see by how much. The limitation to state is the uniform assumption; real arrivals bunch near the hour, which raises the meeting chance.

1/3. Picking a cube at random and then a face at random makes every one of the 27 x 6 = 162 small faces equally likely to end up on top. The painted small faces are exactly the squares on the big cube's surface, 6 faces of 9 each, 54 in all. So the chance is 54/162 = 1/3. The breakdown by cube agrees: corners give 8 x 3, edges 12 x 2, face centres 6 x 1, the core 0, total 54.

Why count faces rather than cubes?

If a bag holds sweets of different sizes and you want the chance a random bite is chocolate, you count chocolate bites, not chocolate sweets. Every small cube is equally likely and every face of it is equally likely to land on top, so every one of the 162 small faces has the same chance, 1/162, and the answer is just the share of small faces that are painted. That share is easy, because the painted small faces are exactly the visible squares of the big cube: 6 faces with 9 squares each, 54. The answer, 54/162 = 1/3, comes in one line without classifying a single cube, which is what the interviewer hopes to see.

How does the cube-by-cube count confirm it?

Classify the 27 cubes by position. The 8 corners have 3 painted faces each, the 12 edge cubes have 2, the 6 face centres have 1, and the single core cube has none: 8 + 12 + 6 + 1 = 27. Weight each type by how often you pick it and by the chance its top is painted: 8/27 x 3/6 + 12/27 x 2/6 + 6/27 x 1/6 + 1/27 x 0 = (24 + 24 + 6) / 162 = 1/3, the same answer by the long road. The two methods are the law of total probability written two ways, once by cube and once by face, and saying that out loud shows you know why they must agree. For an n x n x n cube the face count gives 6n squared painted faces out of 6n cubed, so the answer is 1/n: 1/2 for a 2 x 2 x 2 cube, 1/10 for a 10 x 10 x 10.

What is the natural follow-up, and how do you answer it?

Turn it round: the top face is painted; what is the chance you picked a corner? That is Bayes on the same count. Of the 54 painted faces, 24 belong to corners, so the chance is 24/54 = 4/9, far above the 8/27 a corner has before you look. Seeing paint is evidence for the cubes with more paint, and the face count gives the posterior directly without a formula. A second follow-up asks for the chance that the picked cube has any paint at all, which is 26/27, and the gap between 26/27 and 1/3 is exactly the trap in the original question. The limitation is that the face count relies on every face being equally likely to land on top; a weighted cube, or a rule that picks cubes by size, would need the long route.

About 3.28 loops. Each tie either closes a loop or joins two strands into one longer strand, so after every tie there is one strand fewer. With n strands left there are 2n free ends; pick one, and of the other 2n - 1 ends exactly one belongs to the same strand, so that tie closes a loop with chance 1/(2n - 1). Linearity of expectation adds those chances over n = 100 down to 1: 1/199 + 1/197 + ... + 1/3 + 1.

Why does every tie either close a loop or shorten the list by one strand?

Think of 100 pieces of string on a table. Tie two ends from different pieces and you now have 99 pieces, one of them longer. Tie the two ends of the same piece and you have a ring and 99 pieces left as well. Whatever happens, the number of strands with free ends falls by exactly one per tie, so there are exactly 100 ties, and the only question at each tie is whether it closed a loop. That makes the count of loops a sum of 100 indicator events, which is the signal to use linearity of expectation rather than to enumerate outcomes.

Where does 1/(2n - 1) come from?

With n strands there are 2n free ends. Pick the first end; it belongs to some strand. Of the remaining 2n - 1 ends, exactly one is the other end of that same strand, and all are equally likely, so the tie closes a loop with chance 1/(2n - 1). It does not matter how long the strands have become or how many loops already sit in the bowl, because closed loops have no free ends and are out of the picture. The expectation is therefore the sum of 1/(2n - 1) for n from 100 down to 1, which is the odd-denominator half of the harmonic series.

What is the approximation, and why is the answer so small?

The sum of odd reciprocals up to 1/(2n - 1) is close to half of ln(4n) plus half the Euler constant, which for n = 100 gives 3.28 against the exact 3.284. Doubling the number of noodles adds only about 0.35 to the expected number of loops, so a bowl of a thousand noodles still gives only about four loops. The intuition is that early ties almost never close a loop: they build a few very long strands, and the loops appear at the end when there are only two or three strands left. The limitation is that this is an expectation only; the distribution is skewed, and ending with a single loop is the most likely outcome.

89 ways. Think about the last move. Either it was a single step from step 9 or a double step from step 8, and those two cases cannot overlap, so ways(10) = ways(9) + ways(8). With ways(1) = 1 and ways(2) = 2, the sequence runs 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. It is the Fibonacci rule, shifted by one place.

Why count by the last move rather than the first?

Ask how many ways there are to arrive at a railway junction and you count the lines coming in, not the stations people set out from. Every route to step n arrives from exactly one of two places, step n - 1 by a single or step n - 2 by a double, so the routes to n are the routes to those two places added together. The first move works just as well, but the last move makes the recursion read naturally from the top down, and it is the habit that generalises to harder counting problems where you condition on the final event.

How do you check 89 a second way?

Count by how many doubles you use. With k doubles and 10 - 2k singles you make 10 - k moves in total, and the number of orderings is 10 - k choose k, so the total is the sum over k from 0 to 5 of C(10 - k, k). That is 1 + 9 + 28 + 35 + 15 + 1 = 89, the same answer by a route that does not use the recursion at all. Two methods agreeing is the thing to say out loud; it also hands you the next question, since the terms tell you that four doubles and two singles is the most common shape of route.

Where does this pattern appear in trading, and where does it stop?

In anything built from steps of two sizes: the number of ways a price can move up to a level in ticks of one and two, or the number of paths in a recombining tree. The recursion is also the warm-up for dynamic programming, where the value of a position is built from the values of the positions it can reach, which is how an American option is priced on a lattice. The limitation is that Fibonacci only appears when every move is a one or a two; allow a three-step jump and the rule becomes a sum of the previous three terms, with 274 ways for ten steps.

110 routes. Without the block there are C(10,4) = 210 routes, one for each way of placing 4 ups among 10 moves. A route through (3,2) is a route from (0,0) to (3,2), C(5,2) = 10 ways, followed by a route from (3,2) to (6,4), another C(5,2) = 10 ways, so 100 routes pass through the block. Subtract: 210 - 100 = 110.

Why is a lattice route a choice of positions rather than a sequence of decisions?

Think of a delivery driver in a city laid out as a grid who only ever drives east or north. Whatever order the turns come in, the trip is six blocks east and four blocks north, and the only freedom is which of the ten blocks are the north ones. A monotone route is fully described by choosing which 4 of its 10 moves go up, so the number of routes is 10 choose 4, which is 210, and no decision tree is needed. The same logic prices any question that asks how many ways a count can reach a level in fixed-size steps.

Why does multiplying the two legs count each bad route exactly once?

Because a monotone route visits a given point at most once; it can never come back. A route through (3,2) splits uniquely into the part before the block and the part after, so the number of such routes is the product of the two leg counts, 10 x 10 = 100, with no double counting to correct. Each leg is three rights and two ups, so C(5,2) = 10. If there were two blocked points, the same idea works but needs inclusion and exclusion: subtract the routes through each, then add back the routes through both.

How do you check 110 another way?

Fill the grid with counts. Each point's count is the sum of the counts to its left and below, with the blocked point set to zero, and the corner comes out at 110. That dynamic-programming check takes a minute on paper and catches arithmetic slips in the binomials. It also answers the probability version the interviewer sometimes asks: if each step is right or up with equal chance, the chance a random walk reaches (6,4) at all is not 1, because it can overshoot, so the probability of avoiding the block among routes that do arrive is 110/210, about 52%, which is a different question from the probability for a free walk.

The probability is 1/6, not 1/5. By symmetry the game ends on a 2 one third of the time. A first roll of 1 happens one sixth of the time and leaves all three evens unseen, so 2 is last with probability 1/3. The joint probability is 1/18, and 1/18 divided by 1/3 is 1/6. The naive 1/5 treats the five possible first rolls as equally likely given the ending, and they are not.

Why does the ending change the odds of the start?

Think of a race where you learn only who finished last. If you are told that runner C came last, the start line was still fair, but some starting arrangements make C last more often than others, and you should update towards those. The die works the same way. A first roll of 4 leaves only two evens unseen, so 2 comes last half the time; a first roll of 1 leaves three evens unseen, so 2 comes last only one third of the time. The ending is twice as consistent with a first-roll 4 as with a first-roll 1, and a first-roll 2 is ruled out entirely, because a 2 that has already appeared cannot complete the set.

How do you set up the Bayes calculation in thirty seconds?

Group the first roll into three cases rather than six, because 1, 3 and 5 are interchangeable and so are 4 and 6. Odd first roll: probability 1/2, and then 2 ends the game with probability 1/3, giving a joint weight of 1/6. First roll 2: joint weight 0. First roll 4 or 6: probability 1/3, then 2 ends the game with probability 1/2, joint weight 1/6. The weights add to 1/3, which is the unconditional chance of ending on a 2, as symmetry says they must. Given the ending, the first roll was odd with probability 1/2 and was 4 or 6 with probability 1/2, so each odd face carries 1/6 and each of 4 and 6 carries 1/4.

The sanity check the interviewer wants to hear: 3 x 1/6 + 2 x 1/4 = 1, so the posterior weights over the five possible first rolls add up. Then say the general point. An odd roll is a wasted roll that tells you nothing about which even finishes last, which is why its posterior weight is simply its prior, 1/6, unchanged. The information in the ending all goes into shifting weight from the 2, which is now impossible, onto 4 and 6.

The single deck, 25.49% against 25.24%. The first card is black with probability 1/2 in either deck. The second draw is where they differ: with one deck, 26 reds remain in 51 cards, 50.98%; with two decks, 52 remain in 103, 50.49%. Multiply: 26/52 x 26/51 = 25.49% and 52/104 x 52/103 = 25.24%. Removing a black card tilts a small deck towards red more than it tilts a large one.

Why does the size of the deck matter when the mix is the same?

Take one boy out of a class of 20 with 10 boys and 10 girls, and the class is 10 girls in 19, 52.6% girls. Take one boy out of a school of 2,000 split evenly, and it is 1,000 in 1,999, 50.03%. The same removal is a bigger share of a smaller group. Drawing without replacement makes the second draw depend on the first, and the dependence is stronger the smaller the deck, which is exactly what the game rewards. You want a black card to make red more likely next, and a single deck gives you more of that lean.

What is the general pattern, and what is its limit?

With n decks shuffled together, the chance is 1/2 x 26n/(52n - 1). As n grows the second factor falls towards 1/2 and the product towards 1/4, which is the answer you would get if the draws were independent. Every finite deck beats 25%, and the smallest deck beats it by the most, because the minus one in the denominator is a larger share of a smaller count. The whole effect is small, a quarter of a percentage point between one deck and two, which is also worth saying: the interviewer wants the direction and the reason more than the third decimal.

Then show you can flip it. If the game paid on black followed by black, the single deck would be worse: 26/52 x 25/51 = 24.51% against 52/104 x 51/103 = 24.76%, and the big deck wins. Same mechanism, opposite sign. Saying that unprompted is what turns a one-line puzzle into evidence that you understand sampling without replacement rather than remembering an answer.

One half. By the time the last passenger boards, seats 2 to 99 are always taken, because each owner either sat in theirs or found it taken. The free seat is either seat 1 or seat 100. Every passenger who chooses at random, the first and each one displaced after him, faces seat 1 and seat 100 with exactly the same chance, so the game is equally likely to settle on either. The answer is 1/2 for any plane with two or more seats.

Why do only two seats matter?

Think of a cloakroom where one guest hangs his coat on a random hook. Each later guest uses their own hook if it is free and a random free hook if not. Every hook except two has an owner who will turn up and either use it or find it used. The last passenger can only end up in seat 1 or seat 100, because every seat in between has an owner who boards earlier and leaves it occupied. So the whole question is which of those two seats is still empty when the last passenger walks down the aisle.

Why are the two endings equally likely?

Follow the chain of displaced people. Passenger 1 picks at random. If he takes seat 1, nobody is ever displaced and the last passenger gets seat 100. If he takes seat 100, the last passenger is shut out. If he takes some other seat k, everyone up to k sits normally and passenger k inherits the problem: a random choice among the free seats, which still include both seat 1 and seat 100. Every random chooser in the chain picks seat 1 and seat 100 with equal probability, and the chain stops the moment either is taken, so the two endings carry the same total weight, 1/2 each. The other seats only pass the problem along; they never decide it.

Check it on the smallest case aloud: with two seats, passenger 1 takes his own or the other with equal chance, so 1/2. Running the recursion for every plane from 2 to 100 seats returns exactly 1/2 each time. A useful extension the interviewer often asks next: passenger j, for j from 2 to n, gets their own seat with probability (n - j + 1)/(n - j + 2). Passenger 2 is almost always fine; passenger 99 is fine two times in three. The limitation is in the rules: if displaced passengers preferred seats near the front, the symmetry between seat 1 and seat 100 breaks and so does the half.

For n = 4 it is 8/24 = 1/3; in general it is 2^(n - 1)/n!. A pass moves any number left by at most one place, so the smallest must start first or second. If it starts first, the rest is the same problem on n - 1 numbers. If it starts second, it swaps to the front and whatever was first becomes the head of a fresh problem on n - 1 numbers. Two choices each time give 2^(n - 1) sortable orders out of n!.

What can one pass actually do to an array?

Picture a queue where the tallest person seen so far keeps stepping past whoever is behind them. The tall ones can travel a long way back; everyone else only gets stepped past, and each time that happens they move forward by one place. A single left-to-right pass carries the running maximum to the right and moves every other number left by at most one position. So a number that starts two or more places to the right of where it belongs cannot get home in one pass, and the array cannot come out sorted.

How does that turn into a count of 2^(n - 1)?

Look at where the smallest number starts. It must be position 1 or 2. If it is first, the first comparison does nothing and the pass carries on over positions 2 to n, which is the same problem on n - 1 numbers. If it is second, the first comparison swaps it to the front and the number that was first now leads a pass over positions 2 to n, again the same problem on n - 1 numbers. Each step offers exactly two placements for the current smallest number, so the count of sortable orders doubles with each extra element: f(n) = 2 f(n - 1), f(1) = 1, which gives 2^(n - 1). For n = 4 that is 8 of 24, a third.

Then verify on a case you can hold in your head, as the figure does for three numbers: 4 of 6 come out sorted. A brute-force check over every order up to seven numbers gives 1, 2, 4, 8, 16, 32 and 64 sortable orders, as the formula says. The equivalent condition is worth saying too: one pass sorts the array exactly when every number starts no more than one place to the right of its sorted position. The limitation is the assumption that all n! starting orders are equally likely; a nearly sorted array, which is what real data often is, comes out sorted far more often.