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 remove n 2 tokens from the pile for some nonnegative integer n . If a player cannot make a move, they lose. For how 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 remove n 2 tokens from the pile for some nonnegative integer n . If a player cannot make a move, they lose. For how 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 induction on N . If N = 0, then the first player loses. n 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 winning strategy. If N is not a multiple of 3, the first player can remove either 1 or 2 coins to get the number of coins in the pile down to a multiple of 3, so the first player will always win.