Derivatives Foundation puzzles, solved step by step

Puzzles: 100
Traced to a firm: 66
Topics: 12
Hard: 29

Showing 1–3 of 3 · filtered from 100Clear filters

011n points are dropped at random on a circle of circumference 1. Each point colours in the arc between itself and its nearest neighbour. As n grows large, what fraction of the circle do you expect to be coloured?Probability and countingHardSusquehanna International GroupLondon · 2026

Try it first

First instinct: a gap between two neighbouring points stays blank when?

Show the worked solution

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.

Fourteen random points cut the circle into fourteen gaps; the green gaps are coloured because each is shorter than at least one neighbour, the grey gaps are blank because each beats both neighbours, and in the limit the blank gaps carry 11/18 of the length and the coloured ones 7/18, about 38.9%.

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.

The relationship

E[\max(G_1, G_2, G_3)] = \mu\left(1 + \tfrac{1}{2} + \tfrac{1}{3}\right) = \tfrac{11}{6}\mu \quad\Rightarrow\quad \text{blank} = \frac{\tfrac{1}{3}\cdot\tfrac{11}{6}\mu}{\mu} = \frac{11}{18},\qquad \text{coloured} = \frac{7}{18}

G_1, G_2, G_3	a gap and its two neighbours, approximately independent exponentials for large n
mu	the mean gap, 1/n
1 + 1/2 + 1/3	the expected maximum of three unit exponentials, from the memoryless property

What it says in wordsA gap's expected blank length is a third of the expected longest of three gaps, and dividing by the mean gap gives the blank share of the circle.

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.

Where candidates lose it

The common wrong answer is 2/3, from the count: each gap is the longest of three one time in three, so one third of the gaps are blank. The blank gaps are the long ones, so by length they carry more than a third, 11/18.

The second loss is trying to integrate over the joint distribution of n spacings. The limit is a three-gap problem with exponential gaps, and a desk wants the memoryless argument, not the integral.

What the interviewer asks next

What is the expected number of blank gaps when there are n points?
Now each point colours the arcs to both of its neighbours. What changes?
Why do the gaps between uniform points on a circle look exponential when n is large?

Asked at Susquehanna International Group, Quantitative Research, London, 2026 (Wall Street Oasis): if n points are placed on a circle and each point colours in the arc to its nearest neighbour, what is the expected length of coloured circumference

060A bowl holds 100 cooked noodles. You repeatedly pick two free ends at random and tie them together, until no free ends remain. What is the expected number of loops in the bowl?Probability and countingHardD.E. ShawNew York · 2026
Try it first
100 noodles, 100 ties. Roughly how many loops do you expect at the end?
Show the worked solution
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.
The chance that a tie closes a loop is 1/(2n - 1) with n strands left, so it is 1/199 at the first tie and stays near zero until the last handful, reaching 1/3 and then 1; the running expected total climbs slowly and reaches 3.28 only because the last ten ties alone contribute 2.13.
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.
The relationship
$E[\text{loops}] = \sum_{n=1}^{100} \frac{1}{2n-1} = 1 + \tfrac{1}{3} + \tfrac{1}{5} + \cdots + \tfrac{1}{199} \approx 3.284 \approx \tfrac{1}{2}\ln(4n) + \tfrac{\gamma}{2}$
n the number of strands with free ends before a tie
1/(2n - 1) the chance that tie closes a loop
gamma the Euler constant, about 0.577, in the logarithmic approximation
What it says in wordsThe expected number of loops is the sum of the odd reciprocals up to 1/199, which grows only like half the logarithm of the number of noodles.
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.
Where candidates lose it
Most candidates try to track the configuration of strands, which explodes. The interviewer wants the one observation that each tie closes a loop with chance 1/(2n - 1) regardless of history, and then linearity of expectation.
The second loss is guessing a large number. Say out loud that the early ties almost never close a loop, so the answer is a slowly growing sum, and that the harmonic-style sum of 100 terms is around 3, not 50.
What the interviewer asks next
What is the probability that all 100 noodles end up in a single loop?
Approximately how many noodles would you need for the expected number of loops to reach 5?
What is the variance of the number of loops?
Now you tie ends only across different strands when you can. How many loops then?
Asked at D.E. Shaw, Research, New York, 2026 (Wall Street Oasis): What is the expected number of loops from tying 100 noodles' ends together randomly
090An array of n distinct numbers in random order gets one left-to-right bubble pass: swap the first two if they are out of order, then the new second and third, and so on to the end. What is the probability the array is sorted after that single pass? Work n = 4, then general n.Probability and countingHardJump TradingChicago · 2018
Try it first
Where must the smallest number start for one pass to leave it at the front?
Show the worked solution
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.
Running all six orders of 1, 2 and 3 through one bubble pass sorts the four that start 1 2 3, 1 3 2, 2 1 3 and 3 1 2 and leaves 2 3 1 and 3 2 1 unsorted, because in those two the 1 starts two places too far right, and the same count for four numbers is 8 of 24, which is 2^(n - 1) of n! in general.
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.
The relationship
$P(\text{sorted after one pass}) = \frac{2^{\,n-1}}{n!}, \qquad n=3: \tfrac{4}{6}, \quad n=4: \tfrac{8}{24} = \tfrac{1}{3}, \quad n=10: \approx 0.000141$
2^(n-1) the number of starting orders one pass sorts
n! the number of starting orders in all
What it says in wordsThe sortable orders double with each element while all orders multiply by n, so the chance collapses quickly.
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.
Where candidates lose it
The common loss is answering with the chance that the array was already sorted, 1/n!, or with the chance that the largest ends last, which is 1. One pass always puts the maximum at the end; the question is whether everything else is home too.
The second loss is trying to list the n = 4 cases one by one. With 24 orders you will miss some. Find the rule about how far left a number can move and the count follows in two lines.
What the interviewer asks next
What is the probability the array is sorted after two passes?
What is the expected number of swaps in one pass?
If the pass ran right to left instead, which number would be carried, and does the answer change?
Asked at Jump Trading, Quantitative Research, Chicago, 2018 (Wall Street Oasis): a math problem about the probability an array is sorted after swapping the first two if they're out of order

n	the number of strands with free ends before a tie
1/(2n - 1)	the chance that tie closes a loop
gamma	the Euler constant, about 0.577, in the logarithmic approximation

2^(n-1)	the number of starting orders one pass sorts
n!	the number of starting orders in all

Try it first

Why is the question about gaps and not about points?

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

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

Where candidates lose it

What the interviewer asks next

Try it first

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

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

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

Where candidates lose it

What the interviewer asks next

Try it first

What can one pass actually do to an array?

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

Where candidates lose it

What the interviewer asks next