Hedge Funds puzzles, solved step by step

A proposes 98 for himself, 0 for B, 1 for C, 0 for D and 1 for E. Work backwards. With two pirates, D's own vote is half, so he keeps all 100. With three, C buys E with 1 coin. With four, B buys D with 1 coin. With five, A needs two votes beyond his own and buys the two pirates who get nothing in the four-pirate split, C and E, for one coin each.

Why start from the end?

Planning a train journey, you work back from when you must arrive, not forward from when you wake up. Each pirate votes by comparing the offer with what he would get if the proposal failed, so you can only price a vote once you know the next round's outcome, which means solving the smallest game first and working upwards. That method, backward induction, is the whole puzzle.

How does each round play out?

Two pirates, D and E: D proposes 100 for himself, and his own vote is half, so it passes. Three pirates: C needs one more vote and buys E, who gets nothing in the two-pirate game, for 1 coin: 99, 0, 1. Four pirates: B needs one more vote and buys D, who gets nothing in the three-pirate game: 99, 0, 1, 0. Five pirates: A needs two more votes and buys C and E, both empty-handed in the four-pirate game: 98, 0, 1, 0, 1.

What is the interviewer really testing?

Whether you reason about the alternative each party faces rather than about fairness. A vote costs exactly one coin more than what the voter gets if the deal fails, so the cheapest supporters are the ones with the worst fallback. The same logic runs through any negotiation: a creditor backs a restructuring plan when it beats their recovery in liquidation, and support is cheapest from those whose alternative is worst. State the assumptions: perfect rationality, and a pirate who is indifferent votes against, which is why one coin, not zero, is needed.

14 drops. With k drops available, the first egg should go from floor k: if it breaks, the second egg checks the k minus 1 floors below one at a time. If it survives, you have k minus 1 drops left, so the next gap is one smaller. k drops therefore cover k + (k minus 1) + ... + 1 = k(k + 1)/2 floors. 13 drops cover 91 floors, 14 cover 105, so 14 is the minimum: drop from 14, 27, 39, 50 and so on.

Why does binary search fail here?

Binary search assumes you can keep testing after a failure. With two eggs, the first break leaves you one egg, and one egg can only be used safely by walking up one floor at a time. Once the first egg breaks, every floor below it that has not been ruled out costs one drop of the second egg, so large jumps with the first egg are expensive. Dropping the first egg at floor 50 and seeing it break could cost 49 more drops. It is like searching for a leak with one spare pipe: once the first one bursts, you test the rest slowly.

How do you balance the worst cases?

Make every worst case take the same number of drops. If you allow k drops in total, the first drop should be from floor k, the next k minus 1 floors higher, the next k minus 2 higher, because each first-egg drop used leaves one fewer drop for the second egg's walk. With k = 14 the first egg goes from 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100. If it breaks at 27, the second egg tests 15 to 26: 2 plus 12 is 14 drops. The same count holds at every step.

Say what an interviewer wants beyond the number. The move is to fix the budget of drops and ask how many floors it can cover, rather than fixing the building and searching for a strategy. That reversal is what makes the problem easy, and it generalises: with three eggs and k drops, the floors covered are the two-egg coverage for each smaller budget, plus one per drop, added up, which is why three eggs need only 9 drops for 100 floors.

Weigh four against four first, then mix suspects with coins you already know are genuine so every later weighing splits the cases three ways. There are 24 possibilities, 12 coins each heavy or light, and three weighings have 27 outcomes. If 1 to 4 balances 5 to 8, weigh 9, 10, 11 against three good coins; if not, weigh 1, 2, 5 against 3, 6, 9. The third weighing settles what is left.

How do you know three weighings can be enough?

A game of twenty questions works because each yes or no halves what is left. A balance is better than a yes or no: it answers left heavy, right heavy or balanced. Three weighings give 3 x 3 x 3 = 27 outcomes, and there are 24 cases to tell apart, 12 coins each possibly heavy or light, so a procedure can exist only if every weighing splits the remaining cases into three near-equal groups. That counting sets the design: the first weighing must leave at most 9 cases on every branch.

What do you do after the first weighing tips?

Say the left pan was heavy: the odd coin is 1, 2, 3 or 4 and heavy, or 5, 6, 7 or 8 and light. Weigh 1, 2 and 5 against 3, 6 and 9, moving some suspects across and bringing in a known good coin, so each outcome points to a different small group. Left heavy again means 1 heavy, 2 heavy or 6 light: weigh 1 against 2, and a balance means 6. Right heavy means 3 heavy or 5 light: weigh 3 against a good coin. A balance means 4 heavy, 7 light or 8 light: weigh 7 against 8.

What if the first weighing balances?

Then coins 1 to 8 are genuine and the odd coin is among 9 to 12, still heavy or light. Weigh 9, 10 and 11 against three good coins: a tip tells you both that the odd coin is among the three and whether it is heavy or light, and a balance points to coin 12. After a tip, weigh 9 against 10: if the odd coin is heavy the heavier of the two is it, if light the lighter, and a balance means 11. After a balance, weigh 12 against a good coin to learn heavy or light.

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.

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.

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.