The winners of the 2021 Regeneron Science Talent Search were announced on March 17. (Full disclosure: I was a finalist in this very same competition exactly one eternity ago. You can find me among a gaggle of fellow New Yorkers, if you look closely.)
I am delighted that two of this year’s winners were able to share their favorite puzzles for this week’s column!
Hailing from Portland, Oregon, high school senior Wenjun Hou took a swing at the famed knapsack problem with an algorithm designed to run on a quantum computer. This week, he’s putting quantum mechanics aside and challenging you to a classical game instead:
You and Wenjun are playing a game in which you alternate taking turns, removing pennies from a pile. On your turn, you can remove either one or two pennies from the pile. On Wenjun’s turn, he can remove either two or three pennies. Whoever takes the last penny loses. (If there is only one penny left and it’s Wenjun’s turn, then he skips his turn, which means you will lose). Suppose both you and Wenjun play optimally.
1) If you go first, then what initial numbers of pennies mean you will win the game?
2) If Wenjun goes first, then what initial numbers of pennies mean he will win the game?
If you go first, your last move should leave exactly $2$ pennies. If you leave $1$, you have to go again, per the rules. If you leave $3$, Wenjun will opt to remove only $2$, leaving you with the last.
There are two scenarios, you either remove $1$ or $2$ first.
| Pennies in Pile | First Move (Yours) | ... | Last Move (Wenjun's) |
|---|---|---|---|
| $4n+3$ | $1$ | ... | $2$ |
| $4n+4$ | $2$ | ... | $2$ |
Note that for any whole number $n$, there are $n$ pairs (Wenjun, you) of removals between the First Move (Yours) and Last Move (Wenjun's). Whatever Wenjun removes ($w_n$), you should remove $4-w_n$ to guarantee $2$ left over.
If Wenjun goes first, his last move should leave $1$ or $2$ pennies. If he leaves $3$, you would opt to remove $2$, leaving him with the last.
There are four scenarios, Wenjun removes $2$ or $3$ first, and you remove either $1$ or $2$ last.
| Pennies in Pile | First Move (Wenjun's) | ... | Last Move (Yours) |
|---|---|---|---|
| $4n+3$ | $2$ | ... | $1$ |
| $4n+4$ | $2$ | ... | $2$ |
| $4n+4$ | $3$ | ... | $1$ |
| $4n+5$ | $3$ | ... | $2$ or $1$,$1$ |
Similar to above, for any whole number $n$, there are $n$ pairs (you, Wenjun) of removals between the First Move (Wenjun's) and Last Move (Yours). Whatever you remove ($y_n$), Wenjun should remove $4-y_n$ to guarantee the appropriate $1$ or $2$ left over.
You: $4n+3$ and $4n + 4$
Wenjun: $4n+3$, $4n + 4$, and $4n+5$