Take 1 to 3 matches where the last one loses
Question
Two players alternately remove , or 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 any move can be answered with , eventually leaving the opponent the single last match. So move first unless the starting pile is already , 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