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. 100You have n cars, each with enough fuel to drive 1,000 miles, and cars can transfer fuel to each other on the road. How far can one car get? What happens as n grows?Logic and brainteasersHardMillennium ManagementLondon · 2024

    Try it first

    With 4 cars, how far can one car get?

    Show the worked solution

    1,000 x (1 + 1/2 + 1/3 + ... + 1/n) miles, which grows without limit but only like 1,000 x ln n. Drive all n cars together for 1,000/n miles: together they have burned one tankful, so one car tops up the others and stops. Then n - 1 cars drive 1,000/(n - 1), and so on, until the last car drives a full 1,000. With 4 cars that is about 2,083 miles; with 100, about 5,187.

    Why can the fuel not simply be pooled into one car?

    Each tank holds exactly 1,000 miles of fuel, so one car can never carry more than that at once. Think of porters carrying water across a desert: the helpers walk part of the way, hand over what they can spare, and drop back. The helper cars exist to keep the lead car's tank full for as long as possible, and they can only do that by travelling with it and burning fuel themselves.

    Each helper drops out once its fuel can refill the rest: legs of 1,000/4, /3, /2, /1Car 4stops at 250, fills 3Car 3stops at 583, fills 2Car 2stops at 1,083, fills 1Car 1reaches 2,083 miles1,000/4250 mi1,000/3333 mi1,000/2500 mi1,000/11,000 miHow far one car gets with n cars, milesn = 11,000n = 21,500n = 42,083n = 102,929n = 1005,187
    Four cars drive 250 miles together before one refills the other three and stops, three drive 333 more, two drive 500 more and the last drives a full 1,000, reaching 2,083 miles; ten cars reach 2,929 and a hundred reach 5,187.

    How long is each leg?

    With k cars travelling together on full tanks, drive until the group has burned exactly one tankful, which takes 1,000/k miles. Each tank is then 1/k empty, so the k - 1 cars that continue have (k - 1)/k of a tank of space between them, and the car that stops has exactly (k - 1)/k of a tank left to fill it. The legs are 1,000/n, then 1,000/(n - 1), and so on to 1,000 for the last car alone. With four cars: 250 + 333.3 + 500 + 1,000 = 2,083.3 miles. Dropping each helper the moment its fuel can refill the rest keeps as few cars as possible burning fuel at every mile.

    The relationship
    D(n)=1000∑k=1n1k=1000 Hn≈1000 (ln⁡n+0.577)D(n) = 1000\sum_{k=1}^{n}\frac{1}{k} = 1000\,H_n \approx 1000\,(\ln n + 0.577)
    H_nthe harmonic number, 1 + 1/2 + ... + 1/n
    1000/kthe leg driven while k cars are still moving
    0.577Euler's constant, the gap between H_n and ln n for large n
    What it says in wordsThe distance is 1,000 miles times the sum of one over each number of cars still driving, which grows like the natural logarithm of the number of cars.

    What happens as n grows?

    The harmonic series never stops growing, so with enough cars there is no ceiling on the distance. But it grows only like the logarithm of n: 10 cars reach about 2,929 miles, 100 cars about 5,187, and each further tenfold increase in cars adds only about 2,303 miles. Reaching 5,000 miles takes 83 cars. That is the pattern worth naming in the room: unlimited in principle, very expensive in practice, the same diminishing return you meet whenever each extra unit of effort adds less than the one before.

    Where candidates lose it

    The quick wrong answer is n x 1,000 miles, pooling all the fuel, which ignores that no tank holds more than 1,000 and that helpers burn fuel just keeping up. The opposite slip is 1,000 miles, forgetting that fuel can be passed forward at all.

    The second loss is reaching the harmonic series and then saying the distance levels off, or that it grows in proportion to n. Name the growth rate: like ln n, unbounded but slow.

    What the interviewer asks next

    • With 3 cars, exactly how far can one car get?
    • Cars may now turn back and refuel at the start. Can the lead car get further?
    • Roughly how many cars do you need for one car to travel 5,000 miles?

    Asked at Millennium Management, Investments, London, 2024 (Wall Street Oasis): Suppose you have n cars, each fueled so that they can drive for 1000 miles.