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.

For 10 the chance is 0.2893, and for large targets it settles at 2/7, about 0.286. The total lands on n only by landing on one of the six numbers before it and then rolling the exact gap, so p(n) is the average of the previous six values, starting from p(0) = 1. Running that recursion gives p(10) = 17,492,167/60,466,176. In the long run the total advances 3.5 per roll, so it lands on one number in 3.5.

How do you set up the recursion?

Think of climbing a staircase by jumping one to six steps at a time, each jump picked at random. To stand on step 10 you must at some point stand on one of steps 4 to 9 and then make exactly the right jump. The running total equals n only if it first equals one of n minus 1 down to n minus 6 and then the next roll is exactly the gap, and those six routes cannot both happen, so p(n) is the sum of p(n minus k) times 1/6 for k from 1 to 6. In words, each value is the average of the six before it, with p(0) = 1 because you start at zero and p of a negative number = 0.

Why does it settle at 2/7?

If you walk down a long street taking steps that average 3.5 paving stones, then over a kilometre you will have stepped on about one stone in every 3.5. A long run of rolls moves the total forward 3.5 per roll on average, so the totals visited are a share 1/3.5 = 2/7 of all the numbers passed, and far from the start every number is equally likely to be one of them. That is the renewal argument, and it gives the limit without any recursion. It also explains why the answer is not 1/6: the total does not get one try at each number, it passes every number and either lands on it or steps over it.

Why the hump at 6, and what is the desk point?

Small totals have many routes compared with their distance from zero: you can reach 6 in one roll, or in two, three, up to six rolls. For n from 1 to 6, p(n) = (1/6)(7/6) to the power n minus 1, so it grows each step and peaks at 0.360 at six; after that the averaging takes over and damps the swings. The interview point, often set as a coding task, is dynamic programming: one pass, six additions per number, no enumeration of paths. The limitation to say out loud is that the 2/7 limit needs a fair die and nothing that depends on the total so far; a rule such as skip your turn above 50 breaks it.

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.

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.