HMMT 二月 2011 · TEAM1 赛 · 第 1 题
HMMT February 2011 — TEAM1 Round — Problem 1
题目详情
英文原题
- [ 20 ] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. Alicegoes first, and the players alternate turns. On her turn, each player replaces x – the number writtenon the board – with any real number y , subject to the constraint that 0 < y − x < 1.
(a) [ 10 ] If the first player to write a number greater than or equal to 2010 wins, determine, withproof, who has the winning strategy.
(b) [ 10 ] If the first player to write a number greater than or equal to 2010 on her 2011 th turn or laterwins (if a player writes a number greater than or equal to 2010 on her 2010 th turn or earlier, sheloses immediately), determine, with proof, who has the winning strategy.
解析
英文解析
- In this case, p = (1 , 0) , p = (2 , 1), and p = ( r + s , r ). It is apparent that p = ( F , F ),
0 1 i +1 i i i i i +1 iso the minimum is F .
m +1
(b) The answer is L , where L = 1, L = 3, and L = L + L .
m +1 1 2 i +1 i i − 1
The only integer n satisfying g ( n ) = 1 is 2, as it is the only positive integer n > 1 such that allintegers 1 ≤ i < n divide n . Thus, for m = 1, there is no such second smallest integer.
For m ≥ 2, we once again consider all possible reverse sequences. For any sequence, characterizedby k , . . . , k , if there are at least two k not equal to 1, then we can find a smaller possible value
0 m i
(of r ) not equal to the minimum possible by setting any one of these k to 1. Similarly, if anym +1 ik is at least 3, we can find a smaller possible value not equal to the minimum by setting thisik to be 2. Thus, the second smallest obtainable value of r must occur when k = 1 for alli m +1 i
0 ≤ i ≤ m except for some k which is equal to 2.
We now claim that the value of r is minimized with respect to the above conditions by lettingjmk = 2, and k = 1 for all other 0 ≤ i ≤ m . Doing so yields r = L , with { L } defined as in the
1 i m m +1 ianswer. Before we begin our proof, we first note that letting k = 2 instead yields r = 2 F ,
0 m m +1
which is strictly larger than L (since it is larger for m = 1 , 2, andboth sequences satisfy them +1
same recurrence). We therefore assume that k = 1.
Proof of claim. Our recurrences for pairs give us that r = k r + s , s = r . Thus, we have 0
i +1 i +1 i i i +1 ir = k r + r . Now suppose we have k = 2 for a particular j , and for all i 6 = j, 0 ≤ i ≤ m ,
i +1 i +1 i i − 1 j
Team Round Awe have k = 1. Then we have r = 1 , r = 1 + k , and for 2 ≤ i ≤ m, i 6 = j , we havei 0 1 1
r = r + r . We also have r = 2 r + r .
i i − 1 i − 2 j j − 1 j − 2
By our reasoning in part (a), r = F for i < j . Thus, r = 2 F + F = F + F = Fi i +1 j j j − 1 j +1 j j +2
(where we define F = 1). Expressing r as F − F , we find r = F − F , r =
0 j − 1 j +1 j − 1 j +1 j +3 j − 1 j +2
F − F , r = F − 2 F , and so on. It is easy to show by induction that for i > j , wej +4 j − 1 j +3 j +5 j − 1
have r = F − F F . Thus, to minimize r = F − F F , we must maximizei i +2 i − j − 1 j − 1 m m +2 m − j − 1 j − 1
F F .
m − j − 1 j − 1
We claim that F F ≤ F for 1 ≤ j ≤ m .
m − j − 1 j − 1 m − 2
Proof of claim. It is easy to see (and in fact well-known) that for all positive integers n , F countsnthe number of distinct ways to tile a 1 × n board with 1 × 1 squares and 1 × 2 dominoes. Thus
F F counts the number of ways to tile a 1 × m − 2 board with 1 × 1 squares and 1 × 2
m − j − 1 j − 1
dominoes such that the j − 1 th and j th square are not both covered by the same domino, whichis at most the number of ways to tile a 1 × m − 2 board, as desired.
Since this minimum is reached by letting j = 1, we may conclude that the answer is indeed L .
m +1