Quant puzzles, solved step by step

44/120, about 36.7%, and it tends to 1/e, about 36.8%. Count the orderings with no fixed point by inclusion and exclusion: 5! times (1 - 1 + 1/2! - 1/3! + 1/4! - 1/5!) = 44 of the 120 ways. The bracket is the start of the series for e^(-1), so the answer barely moves with the number of traders: it is within about 0.001 of 1/e at five people and closer still after that.

Why does the answer not go to 0 or to 1?

Think of a secret gift exchange at the office. With more people, each person is less likely to draw their own name, but there are more people who could. Each trader matches with chance 1/n and there are n traders, so the expected number of matches is exactly 1 at every size, and the chance of zero matches settles rather than vanishing. That is why the answer converges to a constant. It is also why the question is asked: it checks whether you can count an event defined by an absence, which needs inclusion and exclusion.

How does inclusion and exclusion give 44?

Count the orderings where at least one trader gets their own card, then subtract. Fix any one trader: 4! orderings each, five traders, 120 in total, but that counts orderings with two fixed traders twice. Alternately subtract and add the counts with one, two, three, four and five traders fixed, and you get 120 - 120 + 60 - 20 + 5 - 1 = 44 orderings with no match. Dividing by 120 gives the probability as 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120, and each term is the e^(-1) series truncated.

How do you check 44 another way?

Use the recursion. Trader 1 takes some other trader's card, say trader j's, in n - 1 ways. Either j takes trader 1's card back, leaving n - 2 traders to derange, or j does not, which is the same as deranging n - 1 traders. So D(n) = (n - 1)(D(n - 1) + D(n - 2)), and from D(1) = 0 and D(2) = 1 you get 2, 9 and then 4 x (9 + 2) = 44. The number of matches is close to Poisson with mean 1 for any decent n, so exactly one match has about the same chance as none: for five traders it is 3/8 = 45/120.

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.

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.

Stop at the first draw of 0.8 or more; the game is worth 0.8 after all fees. Holding x, one more draw improves you by (1 - x)^2 / 2 on average, which equals the 0.02 fee at x = 0.8. Check: you expect 5 draws costing 0.10 in total, and the draw you keep averages 0.90, so the net value is 0.80.

How do you decide whether one more draw is worth it?

Think of hunting for a flat. Each viewing costs you an evening. If the flat in hand is already good, another viewing rarely beats it, and when it does it only beats it by a little. The value of one more look is the chance of beating what you hold times the average margin when you do, and you stop when that falls below the price of looking. With a uniform draw and a current value x, the chance of beating x is 1 - x and the average margin is (1 - x)/2, so the expected gain is (1 - x)^2 / 2.

Why are the threshold and the value the same number?

Because the game has no memory. After a disappointing draw you are back where you started, facing the same game worth V. You should accept a draw exactly when it beats what the fresh game is worth, so the threshold equals the value. This is the same logic as a reservation price: you walk away from any offer below what the next round is worth to you. The arithmetic check is worth saying: with threshold 0.8 a draw succeeds with probability 0.2, so you expect 5 draws and 0.10 of fees, and an accepted draw is uniform on 0.8 to 1 with mean 0.9. The net is 0.9 - 0.10 = 0.8. A seeded simulation of 200,000 games gives 0.800.

What happens as the cost changes?

The threshold is 1 - sqrt(2c), so it responds to the square root of the cost. A fee of 0.005, four times cheaper, only moves the threshold from 0.8 to 0.9. At a fee of 0.5 or more, the threshold hits zero and you take the first draw, because even the first draw's average of 0.5 barely covers what you paid. The limitation of the model is that draws are independent and the distribution is known; if you were learning the distribution as you drew, the first few draws would be worth more than this rule says.

10.6 cards, which is 53/5. Each of the 48 non-aces comes before all four aces with probability 1/5, because among that card and the four aces each is equally likely to be first. So on average 48/5 = 9.6 non-aces precede the first ace, and counting the ace itself gives 10.6. For n cards with m special ones the rule is (n + 1)/(m + 1).

Why isn't the answer 13?

Drop four red counters at random into a line of 48 white ones. Nothing distinguishes the stretch of white before the first red from the stretch between the second and third reds, or the stretch after the last red. The four reds cut the whites into five stretches, and by symmetry each stretch holds the same number on average, 48/5 = 9.6. The answer 13 imagines the aces spread evenly from the top of the deck, but that leaves no room for the stretch after the last ace, which is just as long on average as the others.

How do you make the symmetry argument rigorous?

Use indicators. Pick any non-ace, say the seven of clubs. It is turned before the first ace exactly when it comes first among five cards: itself and the four aces. Those five cards sit in a random order, so that happens with probability 1/5. An expected count is the sum of the probabilities, even when the events depend on each other, so 48 x 1/5 = 9.6 non-aces come first on average and the ace makes it 10.6. The exact sum of the chances that the first ace is later than card k, over k from 0 to 48, gives 53/5 as well, and a seeded simulation of 100,000 shuffles gives 10.63.

The mean hides a skewed shape. The first ace is in the top five cards 34.1% of the time, and the median position is 9, below the mean of 10.6, because a few shuffles bury all four aces deep in the deck and drag the average up. If the interviewer asks for the most likely position, the answer is the very first card: each later position needs every earlier card to be a non-ace, so the chances fall card by card.

How does it generalise, and where is it useful?

With n cards and m special ones, the m specials cut the n - m others into m + 1 gaps, so the first special arrives at (n - m)/(m + 1) + 1 = (n + 1)/(m + 1). Check it with one ace: (52 + 1)/2 = 26.5, the middle of the deck, which is what you would expect. The first spade, with 13 specials, arrives at card 53/14, about 3.79. The same gap symmetry gives the expected wait for the first default in a pool or the first fill among queued orders, provided every ordering is equally likely. That proviso is the limitation: if defaults cluster in time or the deck is stacked, the gaps stop being exchangeable and the rule fails.

168 moves. A random walk that picks uniformly among a square's moves spends time at each square in proportion to its number of moves, its degree. The degrees on a chessboard sum to 336 and a corner has degree 2, so the knight is in that corner 2/336 of the time. The expected return time is the reciprocal, 336/2 = 168.

Why is the time spent on a square proportional to its number of moves?

Think of a town where every road is two-way and a lost tourist picks a road at random at each junction. Big junctions get more visits simply because more roads lead into them. For a random walk on a network of two-way links, the long-run share of time at a point is its number of links divided by the total, because that split sends exactly as much traffic along every link in each direction. Check it on one knight move from square u to square v: the flow is (d_u/336) x (1/d_u) = 1/336, and the flow back is the same, so nothing piles up anywhere.

How do you get 336 quickly and check it?

Tally the move counts by symmetry, as in the figure: four corners with 2, eight squares with 3, twenty with 4, sixteen with 6 and sixteen with 8. For a check, count the moves themselves: every knight move is a diagonal of a 2 by 3 or 3 by 2 rectangle, there are 84 such rectangles on the board, each holds 2 moves, so there are 168 two-way moves and 336 move ends. The answer, 168, happens to equal the number of moves, a coincidence of the corner having exactly two.

What are the limits of the trick?

The rule that return time is one over the long-run share holds for any chain that can reach every state and settles down, which is Kac's lemma. The degree formula for that share needs two-way moves chosen uniformly; if the knight preferred some moves, you would have to solve for the share directly. One more subtlety is worth saying: a knight always changes square colour, so it can only return after an even number of moves, and the chance of being in the corner at a fixed time does not settle down. The average return time is unaffected, and a seeded simulation of 100,000 returns gives 168.0. From a central square with 8 moves the return time is 336/8 = 42.

400. Since 1,000 = 2^3 x 5^3, a number shares a factor with 1,000 exactly when it is divisible by 2 or by 5. There are 500 multiples of 2 and 200 of 5, but the 100 multiples of 10 sit in both lists, so 600 numbers share a factor and 400 do not. Euler's formula agrees: 1,000 x 1/2 x 4/5 = 400.

Which numbers share a factor with 1,000?

Picture a hall of 1,000 people where everyone wearing a red badge or a blue badge is asked to leave. To count who stays, you need the red-badge count, the blue-badge count, and how many wear both, because they would otherwise be counted out twice. Write 1,000 as 2^3 x 5^3: a number shares a factor with it exactly when it is divisible by 2 or by 5, so only two badges matter, and the powers 3 do not add any new conditions. Every multiple of 4 or 8 is already a multiple of 2, and every multiple of 25 or 125 is already a multiple of 5.

Why does the quick product formula work here?

Half of all numbers are odd, and among those, four in five are not multiples of 5. Because 1,000 is a multiple of 10, the numbers 1 to 1,000 contain exactly 100 full blocks of ten, and in each block exactly 4 numbers, 1, 3, 7 and 9, survive both tests, so 100 x 4 = 400. The strip of 1 to 20 in the figure shows the pattern repeating, 8 survivors in 20. The product is exact only when the range is a whole number of such blocks: for 1 to 1,234 it gives 493.6, while a direct count gives 494.

Where does a question like this lead in an interview?

Usually to powers and remainders. Euler's theorem says a number coprime to n, raised to the power phi(n), leaves remainder 1 when divided by n, and that is the engine behind last-digit puzzles: phi(100) = 40, so 3^40 ends in 01 and so does 3^400. It also leads to probability: the chance that two large random integers share no factor tends to 6/pi^2, about 0.608. The habit the question tests is factorising first: once you see only the primes 2 and 5 matter, a counting question becomes a two-circle Venn diagram.