HMMT 二月 2011 · TEAM2 赛 · 第 5 题

英文解析

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 theboard – with any real number y , subject to the constraint that 0 < y − x < 1. The first playerto 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 theboard – with any real number y , subject to the constraint that y − x ∈ (0 , 1). The first player towrite a number greater than or equal to 2010 on her 2011 th turn or later wins. If a player writesa number greater than or equal to 2010 on her 2010 th 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 numberon the board.
   Team Round B
   (a) Barbara has the winning strategy: whenever Alice adds z to the number on the board, Barbaraadds 1 − z . After Barbara’s i th turn, the number on the board will be i . Therefore, after Barbara’s
   2009 th turn, Alice will be forced to write a number between 2009 and 2010, after which Barbaracan 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 numberon the board will be ( i − 1) + a , so after Alice’s 2010 th turn, the number will be 2009 + a . Since
   Barbara cannot write a number greater than or equal to 2010 on her 2010 th turn, she will beforced to write a number between 2009 + a and 2010, after which Alice can write 2010 and winthe 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 isespecially important in number theory, so it is often discussed on the radio or on national TV. (Justkidding). But what is it, exactly? For all positive integers k , ϕ ( k ) is defined to be the number ofpositive integers less than or equal to k that are relatively prime to k . It turns out that ϕ is what youwould 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 muchmore than that to ϕ , as you are about to discover!