Quant puzzles, solved step by step

Bid nothing. If a bid of b is accepted, the owner has told you the company is worth less than b to them, so its value is uniform on 0 to b and averages b/2. In your hands that is 1.5 x b/2 = 0.75b, a quarter less than you paid. Expected profit is (b/100) x (0.75b - b) = -b squared/400, negative for every positive bid. This is the winner's curse in its purest form.

Why does 75 look right and fail?

Picture buying a used car from someone who knows its history while you do not. If they agree to your price at once, that is itself news: sellers of good cars refuse low offers. Acceptance is not random; it happens exactly in the states where the company is worth less than you offered, so the average value you actually receive is the average below your bid, not the average overall. The naive 75 uses the unconditional average of 50 and forgets that you only trade when the owner is happy to sell.

How do you set up the expected profit?

Split it into the chance of a deal and the profit given a deal. A bid of b is accepted with probability b/100; given acceptance the owner's value is uniform on 0 to b, averaging b/2, so your value averages 0.75b and your profit averages minus 0.25b. Multiply: minus 0.25b x b/100, which is minus b squared over 400. At a bid of 50 that is minus 6.25 crore: you win half the time and lose 12.5 crore on average when you do.

When would bidding make sense, and where does this show up on a desk?

The multiplier is the lever. With a multiplier m, the profit given a deal is (m/2 - 1)b, so bidding pays only if you add more than double the owner's value; at exactly 2 you break even, and above 2 you should bid the full 100. On a trading desk the same logic is called adverse selectionThe tendency for the trades you actually get to come from counterparties with better information than you, so they are worse on average than a random trade.: the orders that fill against you are disproportionately the ones from people who know more. A quote that looks profitable against the average counterparty loses against the ones who choose to trade.

Fire into the air. B and C each target the other, the bigger threat, so while both live nobody shoots at you. Aiming in the air gives survival of 2/3 x 3/7 + 1/3 x 1/3 = 25/63, about 39.7%. Aiming at C gives 31.2%, because a hit leaves you in a duel with B shooting first. Aiming at B gives 26.5%, because a hit leaves C, who never misses, to shoot you.

Who does everyone else aim at?

Start with the stronger players, because their choices fix yours. B aims at C, because if B shot you instead, C would kill B next turn for certain; C aims at B, the more dangerous of the two remaining threats. So while all three are alive, nobody is shooting at you. Think of two large firms in a price war while a small competitor stays out of it: the small firm's best move is often to let the giants weaken each other.

How do you work out the two-player duels?

Against B with you shooting first, you win if you hit now, or if both miss and the same duel restarts. Call your survival x: x = 1/3 + (2/3)(1/3)x, so x = 3/7; if B shoots first, you must survive B's first shot, 1/3 of the time, giving 1/7. Against C you get exactly one shot, since C never misses: 1/3 if you shoot first, 0 if C does. Now combine. In the air: B hits C two times in three, giving you the 3/7 duel; otherwise C kills B and you get your one shot at C, 1/3. Total 25/63.

What is the general lesson?

In a game with several players, weakening one rival can hurt you if it frees the strongest remaining player to turn on you. Your best shot is the one that keeps the others focused on each other. Say the limitation too: the answer depends on the hit rates and the order. Change the order of shooting, or let C aim at you, and the tree changes; the interviewer will often change a number or the order to see whether you rebuild the tree or repeat the slogan.

Go second. The player facing 1, 5, 9, 13, 17 or 21 matches loses against good play, and 21 is on that list. Whatever your opponent takes, take 4 minus that, so every round removes exactly 4. They then face 17, 13, 9, 5 and finally 1, and are forced to take the last match.

How do you find the losing positions?

Start from the end of the game, the way you would plan the last few stops of a journey before the first. With 1 match in front of you, you must take it and lose. With 2, 3 or 4, you take enough to leave exactly 1 and win. With 5, every move leaves 2, 3 or 4, each a winning spot for the other player, so 5 loses. A position is losing when every move from it hands your opponent a winning position, and here that happens every 4 matches: 1, 5, 9, 13, 17, 21.

Why does answering with 4 minus k always work?

Your opponent can take 1, 2 or 3; you can always take 3, 2 or 1 in reply. The pair of moves removes exactly 4 matches whatever they chose, so you control the count at the end of every round. From 21 the rounds end at 17, 13, 9 and 5, and then your opponent faces a single match. The number 4 is the maximum take plus one; that is where the period comes from.

A short check you can say aloud: the game has only 21 positions, and marking each as winning or losing from the bottom up, a position wins if any move reaches a losing one, reproduces the list 1, 5, 9, 13, 17, 21. If the pile had been 20, you would go first and take 3 to leave 17. This type of game has a backward inductionSolving a game by working out the best move at the last step first, then the step before, back to the start. solution, and the interviewer mainly wants to hear you build it from the end.

Pick THH; you win 7 times in 8. HHH can only win if the first three flips are all heads, which has chance 1/8. In any other run, the first HHH is preceded by a tail, and that tail with the next two heads spells THH, which is completed one flip before HHH. So THH wins every game except the one that opens with three heads.

Why is this not a fair race between two 1/8 sequences?

Think of two runners on the same track where one always starts one step ahead of the other on the only route to the finish. Their speeds are identical but the race is not even. In a race between patterns, what matters is not how often each appears but which one tends to appear first, and that depends on how the patterns overlap. THH is built from HHH's own first two heads with a tail placed in front, so it ambushes HHH whenever HHH has not already won at the start.

How do you prove 7/8 without a Markov chain?

Look at the first time HHH appears. If it does not start at flip 1, the flip immediately before it must be a tail, because otherwise an earlier HHH would already have appeared. That tail plus the first two heads of the HHH is THH, finished one flip before HHH. So HHH wins only if flips 1 to 3 are heads, chance 1/8, and THH wins otherwise: 7/8. The proof is one sentence, and interviewers want to hear it rather than a transition matrix.

What is the general lesson for the second mover?

This is Penney's gameA coin sequence race in which the second player, choosing after seeing the first, can always pick a sequence that wins more than half the time., and the second player always has an edge because the winning relation among three-flip sequences is not transitive: every sequence has another that beats it. The recipe: take the opponent's first two flips, and put in front of them the opposite of the opponent's second flip. Against HHH that gives THH at 7/8; against HTH it gives HHT at 2/3. In trading terms, a strategy that looks as good as any other in isolation can still lose systematically to one designed around it.

I show heads 3/8 of the time; so should you; and the game is worth -1/8 to you per round. At my mix q, your heads pays 3q - 2(1 - q) and your tails pays -2q + (1 - q). Setting them equal gives q = 3/8, where both pay -1/8. By the same algebra your 3/8 mix makes my choices equal, so neither of us can improve: the table looks fair and is not.

Why do I randomise to make you indifferent, not to help myself?

Think of a penalty taker and a goalkeeper. If the taker shoots left more often than he should, the keeper dives left and gains; any pattern is exploited. In a zero-sum game, the mix that protects you is the one that leaves your opponent with nothing to exploit, which means making every one of their choices pay the same. So I do not pick my heads probability by looking at my own payoffs in isolation; I pick it so that your heads and your tails earn you equal amounts. Then it no longer matters what you do.

How do the two equations give 3/8 and -1/8?

Let q be my chance of heads. Your heads earns 3q - 2(1 - q) = 5q - 2 and your tails earns -2q + 1(1 - q) = 1 - 3q, and they are equal when 8q = 3, at q = 3/8. Plug back in: 5(3/8) - 2 = -1/8. For your side, let p be your chance of heads; my payoffs are the negatives of yours, and because the table is symmetric the same algebra gives p = 3/8. At those mixes, each cell's frequency is HH 9/64, TT 25/64 and the two mismatches 15/64 each: 3(9) + 1(25) - 2(30) = -8, over 64, is -1/8.

Why does a table with equal wins and losses favour me?

Because the cells are not played equally often. Your big win needs both of us on heads, and I can make that cell rare; the mismatches, where I win, happen 30 times in 64 at equilibrium. If I played heads half the time you could earn +1/2 by always showing heads, so a naive 50/50 from me would be a gift. In trading the same idea sets a market maker's quotes: they are placed so that the informed side has no choice that beats the others, not so that the market maker profits on any one trade.