HMMT 十一月 2019 · 团队赛 · 第 4 题
HMMT November 2019 — Team Round — Problem 4
题目详情
英文原题
- [35] Two players play a game, starting with a pile of N tokens. On each player’s turn, they must removen
2 tokens from the pile for some nonnegative integer n . If a player cannot make a move, they lose. Forhow many N between 1 and 2019 (inclusive) does the first player have a winning strategy?
解析
英文解析
- [35] Two players play a game, starting with a pile of N tokens. On each player’s turn, they must removen
2 tokens from the pile for some nonnegative integer n . If a player cannot make a move, they lose. Forhow many N between 1 and 2019 (inclusive) does the first player have a winning strategy?
Proposed by: Milan Haiman
Answer: 1346
The first player has a winning strategy if and only if N is not a multiple of 3. We show this by inductionon N . If N = 0, then the first player loses.
If N is a multiple of 3, then N − 2 is never a multiple of 3 for any n , so the second player has a winningnstrategy.
If N is not a multiple of 3, the first player can remove either 1 or 2 coins to get the number of coins inthe pile down to a multiple of 3, so the first player will always win.