HMMT 二月 2011 · TEAM2 赛 · 第 1 题
HMMT February 2011 — TEAM2 Round — Problem 1
题目详情
- [ 55 ] Tom, Dick, and Harry play a game in which they each pick an integer between 1 and 2011. Tom picks a number first and informs Dick and Harry of his choice. Then Dick picks a different number and 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 whose number 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 equally optimal choices, there are two numbers Tom can pick to maximize his expected profit; what are they? 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 following problems, it may be helpful to note that the norm is multiplicative and that it obeys the triangle inequality. 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).
解析
- [ 55 ] Tom, Dick, and Harry play a game in which they each pick an integer between 1 and 2011. Tom picks a number first and informs Dick and Harry of his choice. Then Dick picks a different number and 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 whose number 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 equally optimal 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), 1 and Tom will win with probability . Picking the number 2 will make the probability of winning at 2011 2 least since Dick and Harry would both be foolish to pick 1, so picking 1006 is suboptimal. It is 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. We will show that of these choices, x = 503 maximizes Tom’s expected profit. The trick is to examine the relationship between Tom’s choice and Dick’s choice. We claim that (a) if x > 503, Dick’s choice is x +1 2013 − x and (b) if x < 503, Dick’s choice is 1341 + b c . Let y denote the number Dick chooses. 3 Proof (a). Note first that if x > 503, 2013 − x is the smallest value of y for which Harry always chooses a number less than x . This is obvious, for if y < 2011 − x , a choice of 2012 − x will give Harry a greater expected profit than a choice of any number less than x , and if y = 2012 − x , Harry never chooses 2012 − x − x a number between x and y since x − 1 > = 1006 − x holds for all integers x greater than 2 503, so, by symmetry, Harry chooses a number less than x exactly half the time. The desired result actually follows immediately because the fact that Harry always chooses a number less than x when y = 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, Harry never chooses a number less than x . The proof is by contradiction. If y ≤ 2011 − x , Harry can obtain greater expected profit by choosing 2012 − x than by choosing any number less than x . If y ≥ 1002 + x , Harry can obtain greater expected profit by choosing any number between x and y than by choosing a number less than x . Hence if Harry chooses a number less than x , x and y must satisfy y > 2011 − x and y < 1002 + x , which implies 2 x > 2009, contradiction. We next claim that x +1 if y ≥ 1342 + b c , then Harry chooses a number between x and y . The proof follows from the 3 x +1 1342+ b c− x x +1 x +1 3 inequality > 2011 − (1342 + b c ), which is equivalent to 3 b c > x − 4, which is 2 3 3 x +1 obviously true. We also claim that if y ≤ 1340 + b c then Harry chooses a number greater than y . 3 x +1 1340+ b c− x x +1 3 The proof follows from the inequality < 2011 − (1340 + b c ), which is equivalent to 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 clear 3 that such a choice of y maximizes Dick’s expected profit. It turns out that the same holds true even if x ≡ 1 (mod 3); the computations are only slightly more involved. We omit them here because they bear 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 choice for 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 B profit, it suffices now to show that if Tom chooses 503, Dick chooses 1509. Since the computations are routine 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’s number 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 him 1 and Dick is th of the way along the set of numbers, which in this case is 503. In a rigorous solution, 4 however, the calculations must be handled with grave care. 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 following problems, it may be helpful to note that the norm is multiplicative and that it obeys the triangle inequality. 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).