HMMT 二月 2011 · TEAM2 赛 · 第 5 题
HMMT February 2011 — TEAM2 Round — Problem 5
题目详情
- (a) [ 20 ] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. The players alternate turns. On her turn, each player replaces x – the number written on the board – with any real number y , subject to the constraint that 0 < y − x < 1. The first player to write a number greater than or equal to 2010 wins. If Alice goes first, determine, with proof, who has the winning strategy. (b) [ 20 ] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. The players alternate turns. On her turn, each player replaces x – the number written on the board – with any real number y , subject to the constraint that y − x ∈ (0 , 1). The first player to write a number greater than or equal to 2010 on her 2011th turn or later wins. If a player writes a number greater than or equal to 2010 on her 2010th turn or before, she loses immediately. If Alice goes first, determine, with proof, who has the winning strategy. Page 1 of 2 The Euler Totient Function [40] The problems in this section require complete proofs . Euler’s totient function, denoted by ϕ , is a function whose domain is the set of positive integers. It is especially important in number theory, so it is often discussed on the radio or on national TV. (Just kidding). But what is it, exactly? For all positive integers k , ϕ ( k ) is defined to be the number of positive integers less than or equal to k that are relatively prime to k . It turns out that ϕ is what you would call a multiplicative function , which means that if a and b are relatively prime positive integers, ϕ ( ab ) = ϕ ( a ) ϕ ( b ). Unfortunately, the proof of this result is highly nontrivial. However, there is much more than that to ϕ , as you are about to discover!
解析
- (a) [ 20 ] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. The players alternate turns. On her turn, each player replaces x – the number written on the board – with any real number y , subject to the constraint that 0 < y − x < 1. The first player to write a number greater than or equal to 2010 wins. If Alice goes first, determine, with proof, who has the winning strategy. (b) [ 20 ] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. The players alternate turns. On her turn, each player replaces x – the number written on the board – with any real number y , subject to the constraint that y − x ∈ (0 , 1). The first player to write a number greater than or equal to 2010 on her 2011th turn or later wins. If a player writes a number greater than or equal to 2010 on her 2010th turn or before, she loses immediately. If Alice goes first, determine, with proof, who has the winning strategy. Solution: Each turn of the game is equivalent to adding a number between 0 and 1 to the number on the board. Team Round B (a) Barbara has the winning strategy: whenever Alice adds z to the number on the board, Barbara adds 1 − z . After Barbara’s i th turn, the number on the board will be i . Therefore, after Barbara’s 2009th turn, Alice will be forced to write a number between 2009 and 2010, after which Barbara can write 2010 and win the game. (b) Alice has the winning strategy: she writes any number a on her first turn, and, after that, whenever Barbara adds z to the number on the board, Alice adds 1 − z . After Alice’s i th turn, the number on the board will be ( i − 1) + a , so after Alice’s 2010th turn, the number will be 2009 + a . Since Barbara cannot write a number greater than or equal to 2010 on her 2010th turn, she will be forced to write a number between 2009 + a and 2010, after which Alice can write 2010 and win the game. The Euler Totient Function [40] The problems in this section require complete proofs . Euler’s totient function, denoted by ϕ , is a function whose domain is the set of positive integers. It is especially important in number theory, so it is often discussed on the radio or on national TV. (Just kidding). But what is it, exactly? For all positive integers k , ϕ ( k ) is defined to be the number of positive integers less than or equal to k that are relatively prime to k . It turns out that ϕ is what you would call a multiplicative function , which means that if a and b are relatively prime positive integers, ϕ ( ab ) = ϕ ( a ) ϕ ( b ). Unfortunately, the proof of this result is highly nontrivial. However, there is much more than that to ϕ , as you are about to discover!