HMMT 二月 2011 · TEAM2 赛 · 第 1 题

英文解析

1. [ 55 ] Tom, Dick, and Harry play a game in which they each pick an integer between 1 and 2011. Tompicks a number first and informs Dick and Harry of his choice. Then Dick picks a different numberand informs Harry of his choice. Finally, Harry picks a number different from both Tom’s and Dick’s.
   After all the picks are complete, an integer is randomly selected between 1 and 2011. The player whosenumber is closest wins 2 dollars, unless there is a tie, in which case each of the tied players wins 1
   dollar. If Tom knows that Dick and Harry will each play optimally and select randomly among equallyoptimal choices, there are two numbers Tom can pick to maximize his expected profit; what are they?
   Answer: 503, 1509 Let x denote the number Tom chooses. By the symmetry of the problem,
   picking x and picking 2012 − x yield the same expected profit. If Tom picks 1006, Dick sees that if he
   1005
   picks 1007, Harry’s best play is to pick 1005, and Dick will win with probability , and clearly this is
   2011
   the best outcome he can achieve. So Dick will pick 1007 (or 1005) and Harry will pick 1005 (or 1007),
   and Tom will win with probability . Picking the number 2 will make the probability of winning at 1
   2011
   least since Dick and Harry would both be foolish to pick 1, so picking 1006 is suboptimal. It is 2
   2011
   now clear that the answer to the problem is some pair ( x, 2012 − x ).
   By the symmetry of the problem we can assume without loss of generality that 1 ≤ x ≤ 1005. Wewill show that of these choices, x = 503 maximizes Tom’s expected profit. The trick is to examine therelationship between Tom’s choice and Dick’s choice. We claim that (a) if x > 503, Dick’s choice isx +1
   2013 − x and (b) if x < 503, Dick’s choice is 1341 + b c . Let y denote the number Dick chooses.
   Proof (a). Note first that if x > 503, 2013 − x is the smallest value of y for which Harry always chooses 3
   a number less than x . This is obvious, for if y < 2011 − x , a choice of 2012 − x will give Harry a greaterexpected profit than a choice of any number less than x , and if y = 2012 − x , Harry never chooses
   2012 − x − xa number between x and y since x − 1 > = 1006 − x holds for all integers x greater than
   503, so, by symmetry, Harry chooses a number less than x exactly half the time. The desired result 2
   actually follows immediately because the fact that Harry always chooses a number less than x wheny = 2013 − x implies that there would be no point in Dick choosing a number greater than 2013 − x ,
   so it suffices to compare Dick’s expected profit when y = 2013 − x with that of all smaller values of y ,
   which is trivial.
   Proof (b). This case is somewhat more difficult. First, it should be obvious that if x < 503, Harrynever chooses a number less than x . The proof is by contradiction. If y ≤ 2011 − x , Harry canobtain greater expected profit by choosing 2012 − x than by choosing any number less than x . Ify ≥ 1002 + x , Harry can obtain greater expected profit by choosing any number between x and ythan by choosing a number less than x . Hence if Harry chooses a number less than x , x and y mustsatisfy y > 2011 − x and y < 1002 + x , which implies 2 x > 2009, contradiction. We next claim thatx +1
   if y ≥ 1342 + b c , then Harry chooses a number between x and y . The proof follows from thex +13
   1342+ b c− xx +1 x +1
   inequality > 2011 − (1342 + b c ), which is equivalent to 3 b c > x − 4, which is 3
   2 3 3
   x +1
   obviously true. We also claim that if y ≤ 1340 + b c then Harry chooses a number greater than y .
   x +13
   1340+ b c− xx +1
   The proof follows from the inequality < 2011 − (1340 + b c ), which is equivalent to 3
   2 3
   x +1 x +1
   3 b c < x + 2, which is also obviously true. Now if x 6 ≡ 1 (mod 3), then we have 3 b c > x − 1,
   3 3
   x +1
   so, in fact, if y = 1341 + b c , Harry still chooses a number between x and y . In this case it is clearthat such a choice of y maximizes Dick’s expected profit. It turns out that the same holds true even 3
   if x ≡ 1 (mod 3); the computations are only slightly more involved. We omit them here because theybear tangential relation to the main proof.
   We may conclude that if x > 503, the optimal choice for x is 504, and if x < 503, the optimal choicefor x is 502. In the first case, y = 1509, and, in the second case, y = 1508. Since a choice of x = 503
   and y = 1509 clearly outperforms both of these combinations when evaluated based on Tom’s expected
   Team Round Bprofit, it suffices now to show that if Tom chooses 503, Dick chooses 1509. Since the computations areroutine and almost identical to those shown above, the proof is left as an exercise to the reader.
   Remark: For the more determined, intuition alone is sufficient to see the answer. Assuming Tom’snumber x is less than 1006, Dick will never pick a number y that makes Harry’s best move y + 1, so
   Harry’s best move will either be x − 1 or anything in between x and y . Clearly Tom does not want
   Harry to pick x − 1, and the biggest number he can pick so that Harry will have to pick in between himand Dick is th of the way along the set of numbers, which in this case is 503. In a rigorous solution,1
   however, the calculations must be handled with grave care.4
   An interesting inquiry is, what is the optimal strategy with n players?
   Complex Numbers [90]
   The problems in this section require only short answers.
   √
   2 2
   The norm of a complex number z = a + bi , denoted by | z | , is defined to be a + b . In the followingproblems, it may be helpful to note that the norm is multiplicative and that it obeys the triangleinequality. In other words, please observe that for all complex numbers x and y , | xy | = | x || y | and
   | x + y | ≤ | x | + | y | . (You may verify these facts for yourself if you like).