Hedge Funds puzzles, solved step by step

Puzzles
100
Traced to a firm
38
Topics
14
Hard
30
Topic
All topicsBetting and sizing5Conditional probability and Bayes7Continuous probability and distributions7Counting and combinatorics7Estimation and mental maths4Expected value and dice games8Logic and brainteasers10Market making and trading games6Options and payoffs5Portfolio and risk maths8Random walks and Markov chains7Returns, compounding and fees7Statistics and estimation11Valuation, accounting and macro riddles8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 042A bowl holds 100 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?Counting and combinatoricsHardD.E. ShawNew York · 2026

    Try it first

    Roughly how many loops?

    Show the worked solution

    About 3.28 loops. With k strands in the bowl there are 2k free ends. Pick any end; the other end you pick is one of the remaining 2k minus 1, and exactly one of those belongs to the same strand, so this tie closes a loop with chance 1/(2k minus 1). Either way the number of strands falls by one. Adding 1/199 + 1/197 + ... + 1/3 + 1 gives about 3.284.

    What does one tie do, whatever happens?

    Start with the bookkeeping, because it makes the rest easy. Every tie reduces the number of loose strands by exactly one: either it closes a strand into a loop, or it joins two strands into one longer strand. So there are always exactly 100 ties, and with k strands left there are 2k free ends. The question becomes how many of those 100 ties happen to close a loop.

    What is the chance a given tie closes a loop?

    Think of a room of dancers holding hands in lines: grab one free hand, then pick a second free hand at random, and a circle forms only if the second hand is at the other end of the same line. With 2k free ends, the second end is one of 2k minus 1, and exactly one of them is the other end of the strand you picked, so the chance is 1/(2k minus 1). Give each tie an indicator that is 1 if it closes a loop; by linearity of expectation the expected number of loops is the sum of the chances, from 1/199 for the first tie up to 1 for the last.

    Each tie's chance of closing a loop: tiny for 90 ties, large only at the end00.51first tie: 1/199, 0.5%1/51/3last tie: 1Tie number 1 to 100 (chance this tie closes a loop)0123Running total of expected loopsafter 90 ties: 1.15all 100 ties3.28
    The first tie closes a loop with chance 1 in 199 and the chances stay tiny until the last few ties, 1/5, 1/3 and 1, so the expected number of loops from 100 noodles is only 3.28, about a third of it from the last three ties.
    The relationship
    E[loops]=∑k=110012k−1=1+13+15+⋯+1199≈3.28E[\text{loops}] = \sum_{k=1}^{100} \frac{1}{2k-1} = 1 + \tfrac13 + \tfrac15 + \dots + \tfrac{1}{199} \approx 3.28
    kthe number of strands in the bowl before a tie
    1/(2k-1)the chance that tie joins the two ends of one strand
    What it says in wordsAdd each tie's chance of closing a loop to get the expected number of loops.

    For a sense check without a calculator: the sum of odd reciprocals up to 1/(2n minus 1) is about half of ln n plus ln 2 plus half of Euler's constant, which for n = 100 gives 3.28. The number of loops grows only like the logarithm of the number of noodles: a million noodles would give only about 7.9 loops.

    Where candidates lose it

    The first loss is trying to track the lengths of the strands, which quickly becomes impossible. The length of a strand never matters; only the count of strands does.

    The second loss is getting 1/(2k minus 1) right but summing it wrong, for example as 100 x 1/199. Write the sum out from the last tie backwards, 1 + 1/3 + 1/5, and the size of the answer becomes obvious.

    What the interviewer asks next

    • What is the variance of the number of loops?
    • What is the probability that you end with exactly one big loop?
    • How does the answer grow with the number of noodles, roughly?

    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