HMMT 十一月 2021 · 团队赛 · 第 8 题
HMMT November 2021 — Team Round — Problem 8
题目详情
- [50] Paul and Sara are playing a game with integers on a whiteboard, with Paul going first. When it is Paul’s turn, he can pick any two integers on the board and replace them with their product; when it is Sara’s turn, she can pick any two integers on the board and replace them with their sum. Play continues until exactly one integer remains on the board. Paul wins if that integer is odd, and Sara wins if it is even. Initially, there are 2021 integers on the board, each one sampled uniformly at random from the set m { 0 , 1 , 2 , 3 , . . . , 2021 } . Assuming both players play optimally, the probability that Paul wins is , where n m, n are positive integers and gcd( m, n ) = 1. Find the remainder when m + n is divided by 1000.
解析
- [50] Paul and Sara are playing a game with integers on a whiteboard, with Paul going first. When it is Paul’s turn, he can pick any two integers on the board and replace them with their product; when it is Sara’s turn, she can pick any two integers on the board and replace them with their sum. Play continues until exactly one integer remains on the board. Paul wins if that integer is odd, and Sara wins if it is even. Initially, there are 2021 integers on the board, each one sampled uniformly at random from the set m { 0 , 1 , 2 , 3 , . . . , 2021 } . Assuming both players play optimally, the probability that Paul wins is , where n m, n are positive integers and gcd( m, n ) = 1. Find the remainder when m + n is divided by 1000. Proposed by: David Vulakh Answer: 383 Solution: We claim that Paul wins if and only if there are exactly 1 or 2 odd integers on the board at 2021 2021+ ( ) 2 the start. Assuming this, the answer is . Since the numerator is odd, this fraction is reduced. 2021 2 2021 2021 21 2 Now, m + n ≡ 2 + 21 + 2021 · 1010 ≡ 231 + 2 ≡ 231 + 2 ≡ 231 + 2 · 1024 ≡ 231 + 2 · 576 ≡ 383. Now, observe that only the parity of the integers matters, so we work mod 2, replacing all odd integers with ones and even integers with zeros. Also, note that on Paul’s turn, there are always an odd number of numbers on the board, and vice versa. If the number of ones on the board ever becomes 1, Paul can win, since Sara cannot change the number of ones on the board, while Paul can replace 2 zeros with 1 zero, since Paul will always be given at least 3 numbers on his turn. Moreover, if at the beginning there are 2 ones, Paul can replace them with 1 one and win in the same manner. Obviously, if at any point the board only contains zeroes, Sara wins. Now suppose the number of ones on the board is initially at least 3. Call a state good if there are at least 3 ones and at least 1 zero. We now make the following claims: Claim. If Paul ever acts on a good state so that the result is no longer good, Sara can force a win. Proof. Paul cannot erase all the zeros from the board. Also, Paul can decrease the number of ones on the board by at most 1. Therefore, the only way this can happen is if, as a result of Paul’s move, the number of ones drops from 3 to 2. However, in the case, Sara can replace the 2 ones with a zero on her next turn, making the board contain all zeros, guaranteeing a Sara victory. Claim. If the current state of the game is good, Sara can make a move that results in a good state, with the exception of 1110, in which case Sara can win anyway. Proof. If there are at least 2 zeros, Sara can act on those. If there are at least 5 ones, Sara can replace 2 ones with a zero. If none of these are true, then there must be at most 1 zero and at most 4 ones. Since Sara will always have an even number of numbers on the board on her turn, the state must be
- In this case, she may replace a one and a zero with a one, giving Bob the state 111. The only move for Bob is to change the state to 11, after which Alice wins following her only move. As a result of these claims, if the state of the board ever becomes good, Sara can force a win. Now, if at the beginning there are at least 3 ones, the state is either good already. Otherwise, the state consists of 2021 ones. In the latter case, Paul must change the state to 2020 ones, after which Sara can replace 2 ones with a zero, making the state 2018 ones and 1 zero. Since 2018 ≥ 3, the state is now good and therefore Sara can force a win.