返回题库

HMMT 十一月 2019 · 团队赛 · 第 4 题

HMMT November 2019 — Team Round — Problem 4

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [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?
解析

英文解析

  1. [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.