Quant puzzles, solved step by step

Puzzles
100
Traced to a firm
71
Topics
12
Hard
30
Topic
All topicsLogic and algorithmic reasoning10Conditional probability and Bayes7Counting and combinatorics8Continuous and geometric probability9Correlation, regression and linear algebra9Market making, betting and sizing9Expected value and optimal stopping9Statistics and estimation9Pricing, options and index maths7Games and strategic reasoning8Markov chains and random walks7Mental maths and number sense8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 033There are 21 matches on the table. Two players alternate taking 1, 2 or 3 matches, and whoever takes the last match loses. Would you rather go first or second, and what is your strategy?Games and strategic reasoningWarm upQuant tradingProp trading firms

    Try it first

    First or second?

    Show the worked solution

    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.

    Losing positions for the player to move: 1, 5, 9, 13, 17, 21Matches left before a move212019181716151413121110987654321one round = 4one round = 4one round = 4one round = 4one round = 4Sample play, you moving second:21 left: they take 3, leaving 18; you take 1, leaving 1717 left: they take 2, leaving 15; you take 2, leaving 1313 left: they take 1, leaving 12; you take 3, leaving 9Go second.If they take k, you take 4 - k.Every round removes exactly 4, sothey face 17, 13, 9, 5 and finally 1.
    Counting down from 21, the positions 21, 17, 13, 9, 5 and 1 lose for the player about to move; moving second and answering each take of k with 4 minus k keeps the opponent on those positions until they must take the last match.

    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.

    Where candidates lose it

    The usual loss is playing forward: taking a few matches and hoping to spot the pattern mid-game. Under time pressure that becomes guessing. Work back from one match and the period of 4 appears in three steps.

    The other slip is copying the rule for the version where taking the last match wins. There the losing spots are multiples of 4, and 21 means you should go first and take 1. Read which way the last match counts before you answer.

    What the interviewer asks next

    • What if taking the last match wins instead?
    • What if each player may take 1 to 4 matches?
    • What if there are two piles and you may take any number from one pile?