Quant puzzles, solved step by step

Two on a 4 by 4 board and 10 on a 5 by 5 board. Place one queen per row, trying columns left to right, and abandon a branch the moment the next row has no safe column. On 4 by 4 this visits 16 placements and finds columns 2, 4, 1, 3 and 3, 1, 4, 2. On 5 by 5 the same search visits 53 placements, against 3,125 boards for brute force.

How do you organise the search so it stays small?

Think of filling a seating plan for a wedding where some guests cannot sit near each other. You seat table by table, and the moment a table has no acceptable guest left you undo the previous choice instead of finishing a doomed plan. Backtracking builds the answer one decision at a time and abandons a partial answer as soon as it breaks a rule, so it never enumerates the boards that fail early. For queens, two rules come free from the structure: one queen per row, and one per column, which leaves only the diagonals to check at each step.

How does the 4 by 4 search actually run?

Start with the corner. A queen in column 1 of row 1 leaves row 2 only columns 3 and 4, and both paths run out of safe squares by row 3 or row 4, so no solution uses a corner queen. A queen in column 2 forces column 4 in row 2, then column 1 in row 3 and column 3 in row 4, which works. Columns 3 and 4 are mirror images of 2 and 1. So there are exactly two solutions, and they are reflections of each other. Saying the symmetry out loud halves the work and is exactly what an interviewer building up from a base case wants to hear.

What changes on 5 by 5, and how does the method scale?

The larger board has more room, and every row 1 column leads somewhere. The same search finds 10 solutions after 53 placements, while brute force over one queen per row would test 3,125 boards. On 8 by 8 it finds all 92 solutions in 2,056 placements out of 16,777,216 one-per-row boards. In code, keep three sets, used columns, used down-diagonals (row minus column) and used up-diagonals (row plus column), so each safety check is constant time.

About 28.9%, roughly 29%. Under 2 and 20 the manager earns Rs 20 crore of management fee plus 20% of the remaining Rs 80 crore gain, Rs 36 crore in all. At 1% the management fee is Rs 10 crore and the gain left is Rs 90 crore, so the performance fee must bring in Rs 26 crore: 26 / 90 = 28.9%. It only balances at a 10% return.

Why is the answer not simply 30%?

Think of a shopkeeper who takes a fixed rent from a stall plus a fifth of whatever the stall-holder clears after paying that rent. If the rent is halved, the stall-holder clears more, and the shopkeeper's fifth is a fifth of a larger amount. Cutting the management fee enlarges the gain on which the performance fee is charged, so part of the lost management revenue comes back automatically. Here the old fee of 20% on Rs 90 crore earns Rs 18 crore, up from Rs 16 crore, and the true shortfall is Rs 8 crore, not Rs 10 crore. Adding 10 points to get 30% repays the shortfall twice over in part.

How do you set it up in one line?

Write revenue as management fee plus performance rate times the gain after the management fee, and hold it equal. The new rate is the old revenue less the new management fee, divided by the new fee base: (36 - 10) / 90 = 28.9%. The investor's position is the mirror image: gross gain Rs 100 crore less Rs 36 crore of fees leaves Rs 64 crore, a 6.4% net return under either set of terms, which is a good check that you have kept the total fixed.

What does the swap change, even when revenue matches?

The match holds at one return only. Swapping management fee for performance fee moves risk onto the manager: less is guaranteed, more depends on the year. At a 5% gross return the old terms pay Rs 26 crore and the new ones Rs 21.6 crore; at 20% the old terms pay Rs 56 crore and the new ones Rs 64.9 crore. State the convention too: if the performance fee were charged on the gross gain instead, the old revenue is Rs 40 crore and the new rate comes to exactly 30%. Say which convention you assume before giving a number.

9 steps. Let E(k) be the expected steps left from state k. Each step costs one and lands on a neighbour with equal chance, so E(k) = 1 + (E(k - 1) + E(k + 1))/2, with E(3) = E(-3) = 0. The solution is E(k) = (3 - k)(3 + k): 9 from 0, 8 from plus or minus 1, 5 from plus or minus 2. A symmetric walk needs about the square of the distance to travel it.

Why is the answer not 3?

Think of someone pacing a narrow corridor, choosing left or right at random with every step. They do reach a wall eventually, but they spend most of their time doubling back. A random walk with no drift covers distance like the square root of time, so covering a distance of 3 takes about 3 squared steps, not 3. The answer 3 would only be right if the walk always moved in one direction. The structure to name in the room is a first-step recursion on the state, which turns the question into seven unknowns with simple links between them.

How do you solve the recursion quickly?

Use symmetry first: E(1) = E(-1) and E(2) = E(-2). Then three equations remain. From 2: E(2) = 1 + (E(1) + 0)/2. From 1: E(1) = 1 + (E(0) + E(2))/2. From 0: E(0) = 1 + E(1), because both neighbours are worth E(1). Substituting gives E(1) = 8 and E(0) = 9, and every value matches the product of the distances to the two walls. The second differences of E are all minus 2, which is why the answer is a parabola: each step must remove exactly one unit of expected time.

How do you check 9 a second way?

Use a martingaleA process whose expected next value, given everything so far, equals its current value: a fair game.. Squaring the position and subtracting the number of steps gives a fair game, because each step adds exactly 1 to the expected square. At the moment the walk stops its square is exactly 9, so the expected number of steps must also be 9. The same argument handles uneven walls: starting between -a and +b, the expected time is a times b. The cousin result is the hitting probability: from +1, the walk reaches +3 before -3 with probability 2/3, the distance to the far wall over the total width.

Macaulay duration is 1.943 years and modified duration is 1.833. At par the yield equals the coupon, 6%. The year 1 coupon is worth 6 / 1.06 = 5.660 and the final payment 106 / 1.06^2 = 94.340, adding to 100. Weight each time by its share: 0.0566 x 1 + 0.9434 x 2 = 1.943. Divide by 1.06 for modified duration: a 1 point rise in yield cuts the price by about 1.83%.

What is Macaulay duration actually measuring?

Think of a seesaw with weights placed along it at the dates money arrives, each weight equal to what that payment is worth today. Macaulay duration is the point where that seesaw balances: the average time to your money, weighted by present value. A zero-coupon bond has all its weight at maturity, so its duration equals its maturity. Any coupon puts a little weight earlier and pulls the balance point forward. Here the coupon is small and the bond is short, so the pull is small, and that is the whole shape of the answer before any arithmetic.

How do you get the numbers fast in your head?

At par, the yield is the coupon, so discount at 6%. The coupon's present value, 6 / 1.06, is about 5.66, and the rest of the price, 94.34, sits at year 2, so duration is 2 minus the coupon's weight: 2 - 0.0566 = 1.943. That shortcut works for any two-period bond: start at the maturity and subtract the early weight times the time it saves. For a par bond there is also a closed form, (1 + y)/y times (1 - 1/(1 + y)^n), which gives the same 1.9434.

Why are there two durations, and how good is the estimate?

Macaulay duration is a time; modified duration is a slope. Modified duration is the percentage price change for a one point change in yield, so this bond loses about 1.83% if yields rise from 6% to 7%, about Rs 0.018 per Rs 100 for each basis point. Repricing exactly gives 98.192 at 7%, a fall of 1.808%, and 101.859 at 5%, a rise of 1.859%. The rise is bigger than the fall, which is convexityThe curvature of the price against yield: prices rise more when yields fall than they drop when yields rise by the same amount.; for a two-year bond it is a small correction, for a thirty-year bond it is not.

Decline it: same colour comes up 25 times in 51, so the bet loses about Rs 1.96 per Rs 100. Whatever the first card is, 25 of the remaining 51 share its colour and 26 do not. The bet is fair only if a win pays Rs 26 for every Rs 25 risked, that is Rs 104 on a win against Rs 100 on a loss.

Why is same colour less likely than different colour?

Imagine a classroom with 26 girls and 26 boys. Pick one child, then pick a second: the second is slightly more likely to be of the other sex, because the first pick removed one of their own. Drawing without replacement makes the second card lean away from the first card's colour, since that colour is now short by one. The first card is irrelevant to the answer, whichever colour it is. Only what is left in the deck matters: 25 matching cards and 26 non-matching.

What is the bet worth, and what makes it fair?

Expected value is the win times its chance less the loss times its chance: 100 x 25/51 - 100 x 26/51 = -100/51, about Rs -1.96. A bet is fair when the payout ratio equals the odds against winning, here 26 to 25, so the win must pay Rs 104 for each Rs 100 at risk. Quoting it as odds rather than a probability is how a trader would answer: you would take the bet at 26 to 25 or better, and decline anything worse.

Why would an interviewer offer such a small edge?

To see whether you notice it at all, and then whether you size your response to it. An edge of about 2% per bet is small for one play but decisive over many, so the right answer is to decline at even money and quote the price at which you would play. It also tests whether you separate the first card, which is free, from the conditional chance of the second. With replacement, or with an infinite deck, the bet would be exactly fair; the whole edge comes from the deck being finite, and it shrinks as more decks are shuffled together.

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.

About 1, 3, 6 and 12 correct digits: the count roughly doubles each step. The update is x(next) = (x + 2/x)/2: 1.5 gives 17/12 = 1.41667, then 577/408 = 1.4142157, then 665857/470832 = 1.41421356237469. Each new error is about the old error squared divided by 2x, so if the error is 10^-k, the next is about 10^-2k. That is quadratic convergence.

Where does the update rule come from?

Think of guessing a side of a square room whose area is 2. If your guess is too big, 2 divided by your guess is too small, and the truth sits between the two. Newton's method for x squared minus 2 is exactly that: replace x with the average of x and 2/x. Formally, Newton follows the tangent of f(x) = x^2 - 2 down to zero, x - f(x)/f'(x) = x - (x^2 - 2)/(2x), which simplifies to (x + 2/x)/2. The averaging form is the one to use in your head.

How do you get the iterates without a calculator?

Keep fractions. From 3/2, the next value is (3/2 + 4/3)/2 = 17/12, then (17/12 + 24/17)/2 = 577/408, and the pattern continues: if x = p/q, the next is (p^2 + 2q^2)/(2pq). 17/12 is 1.41667, already right to 1.41. 577/408 is 1.4142157 against 1.4142136, right to 1.41421. The third step's fraction, 665857/470832, is too big for mental division, but you can predict its accuracy without doing it, which is the point of the question.

Why is it the digits that double, and when does that fail?

Subtract the root from the update and the algebra collapses to (x - root 2)^2 / 2x. Squaring an error of 10^-3 gives 10^-6, so each step doubles the number of correct digits once you are close. The errors here run about 0.09, 0.0025, 2 x 10^-6 and 1.6 x 10^-12. The doubling needs a good start and a simple root: far from the root, or where the slope is zero, Newton can creep or jump away. Bisection, by contrast, gains one binary digit per step whatever happens, which is why desk code often brackets with bisection and finishes with Newton when solving for implied volatility.

1/6. Let D be the distance to the nearest edge. D exceeds d exactly when the point lies in the inner square of side 1 - 2d, so P(D > d) = (1 - 2d)^2 for d up to 1/2. The expected value of a non-negative variable is the integral of its tail, and the integral of (1 - 2d)^2 from 0 to 1/2 is 1/6.

Why work with the chance of being far rather than the distance itself?

Think of a sandpit where a child stands at a random spot and the question is how far they are from the nearest edge. Writing the distance as min(x, 1 - x, y, 1 - y) and integrating a minimum of four things means splitting the square into four triangles. Asking instead when the point is farther than d from every edge has a one-picture answer: the point must lie in a smaller square, shrunk by d on every side. That square has side 1 - 2d, so its area, (1 - 2d)^2, is the tail probability. One formula replaces four cases.

How does the tail give the expectation?

For any non-negative random variable, the expected value equals the integral of the chance that it exceeds each level, E[D] = integral of P(D > d). Here that is the integral of (1 - 2d)^2 from 0 to 1/2. Substitute u = 1 - 2d and it becomes half the integral of u^2 from 0 to 1, which is 1/6. A simulation with 200,000 random points gives 0.1669, against the exact 0.1667.

How do you sanity-check 1/6 against simpler cases?

Build up the number of edges. The distance to one fixed edge averages 1/2, to the nearer of two opposite edges averages 1/4, and to the nearest of all four it falls to 1/6, so each added constraint pulls the minimum closer. The density of D is the slope of the tail, 4(1 - 2d), largest at the edge, which says most random points are near the boundary. That is the same reason most of the volume of a high-dimensional cube sits near its surface, a fact that matters when sampling scenarios in many risk factors at once.

A^10 has 29,525 on the diagonal and 29,524 off it. A has eigenvalue 3 along (1, 1) and eigenvalue 1 along (1, -1). Writing A = Q D Q^T with D = diag(3, 1), the tenth power is Q D^10 Q^T, and only the numbers 3 and 1 get raised to the tenth. The entries are (3^10 + 1)/2 and (3^10 - 1)/2.

Why look for eigenvectors at all?

Think of a photocopier set to 300% on one axis and 100% on the other. Copy a copy ten times and you do not need to simulate every pass: that axis is 3 to the tenth times longer and the other is unchanged. An eigenvector is a direction the matrix only stretches, so applying the matrix ten times along it is just multiplying by the eigenvalue ten times. Symmetric matrices always have a full set of such directions at right angles, which is what makes this matrix easy.

Find them by inspection. Adding the two rows of A gives 3 in each, so A(1, 1) = (3, 3): eigenvalue 3. Subtracting gives 1, so A(1, -1) = (1, -1): eigenvalue 1. The trace is 4 and the determinant is 3, and 3 + 1 = 4 and 3 x 1 = 3, which confirms both in one line.

Is there an even faster route for this particular matrix?

Yes. Write A = I + J, where J is the all-ones matrix. J squared is 2J, so every power of J is a multiple of J, and (I + J)^n collapses to I + ((3^n - 1)/2) J. For n = 10 that is I + 29,524 J, which gives 29,525 on the diagonal and 29,524 off it: the same answer, and a good cross-check to say aloud. A brute-force multiplication in code agrees exactly.

Say why this matters on a desk. A covariance matrix with equal variances and one common correlation has exactly this shape, and its eigenvectors are the market direction and the spread directions. Powers of transition matrices in Markov chains are computed the same way, and the eigenvalue closest to 1 tells you how fast the chain forgets where it started.

110 paths avoid the block, so the probability is 110/210 = 11/21, about 52.4%. All shortest paths use 6 rights and 4 ups in some order: C(10,4) = 210. Paths through (3,2) combine 10 ways in with 10 ways out, 100 in all. Subtract, and 110 survive.

How do you count all the shortest paths?

A shortest path is a string of 10 moves with exactly 6 rights and 4 ups, like a ten-letter word made of R and U. Choosing which 4 of the 10 slots are ups fixes the path completely, so there are C(10,4) = 210 shortest paths. That is the whole sample space, and every one of those strings is equally likely by the question's rule.

Why multiply for the paths through the blocked point?

Think of a trip from home to the office with a stop at a coffee shop. If there are 10 routes to the shop and 10 routes from the shop to the office, there are 10 x 10 = 100 full trips, because every first half pairs with every second half. Paths through (3,2) split the same way: C(5,2) = 10 in and C(5,2) = 10 out, so 100 of the 210 pass through the block. Subtract and 110 remain.

The grid method in the figure is the check, and it is also what you would code. Each point's count is the count from the left plus the count from below, because the last step into any point came from one of those two neighbours. Setting the block to zero removes every path through it automatically, and the same method handles several blocks, where the subtraction formula needs inclusion and exclusion.

Does the answer change if the walker flips a coin at each step?

Yes, and interviewers often ask this next. If the walker flips a fair coin for right or up at each step, any visit to (3,2) happens on move five, and a walker still able to get there has not yet touched the top or right edge, so all five of those moves were free coin flips. The chance of standing on (3,2) after five flips is C(5,2)/2^5 = 10/32 = 5/16, so the coin-flip walker avoids the block with probability 11/16, about 68.8%, well above 11/21. Choosing uniformly among complete paths is not the same as flipping coins: conditioning on the end point (6,4) pulls paths towards the diagonal that leads there, and (3,2) sits on it. Say which model the question means before you answer.