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. Alice goes first, and 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. (a) [ 10 ] If the first player to write a number greater than or equal to 2010 wins, determine, with proof, who has the winning strategy. (b) [ 10 ] If 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 earlier, she loses 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 i so 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 all integers 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, characterized by 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 any m +1 i k is at least 3, we can find a smaller possible value not equal to the minimum by setting this i k to be 2. Thus, the second smallest obtainable value of r must occur when k = 1 for all i m +1 i 0 ≤ i ≤ m except for some k which is equal to 2. j We now claim that the value of r is minimized with respect to the above conditions by letting m k = 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 i answer. 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 the m +1 same recurrence). We therefore assume that k = 1. 0 Proof of claim. Our recurrences for pairs give us that r = k r + s , s = r . Thus, we have i +1 i +1 i i i +1 i r = 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 A we have k = 1. Then we have r = 1 , r = 1 + k , and for 2 ≤ i ≤ m, i 6 = j , we have i 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 = F i 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 , we j +4 j − 1 j +3 j +5 j − 1 have r = F − F F . Thus, to minimize r = F − F F , we must maximize i 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 counts n the 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 − 1th and j th square are not both covered by the same domino, which is 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