Skip to content

Take 1 to 3 matches where the last one loses

Question

Two players alternately remove 11, 22 or 33 matches from a pile, and the player forced to take the final match loses. What is the optimal strategy?

Short answer

Always leave your opponent a number of matches that is one more than a multiple of 4. From 4m+14m+1 any move kk can be answered with 4−k4-k, eventually leaving the opponent the single last match. So move first unless the starting pile is already ≡1(mod4)\equiv1\pmod 4, in which case you want to go second.

Adapted from Joshi, Denson & Downes, Quant Job Interview Questions and Answers, Q8.23, p.278; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question