HMMT 二月 2011 · TEAM1 赛 · 第 10 题
HMMT February 2011 — TEAM1 Round — Problem 10
题目详情
- [ 20 ] Once it has been demonstrated that lim p (0) exists and is greater than 0, it follows that n n →∞ ∞ ∑ lim p ( k ) exists and is greater than 0 for all even positive integers k and that A = 1. It also n 2 k n →∞ k =0 follows that A = a A + a A + a A , A = b A + b A + b A + b A , and A = c A + c A + 0 1 0 2 2 3 4 2 1 0 2 2 3 4 4 6 2 j 1 2 j − 2 2 2 j c A + c A for all positive integers j ≥ 2, where a , a , a , b , b , b , b , and c , c , c , c are the 3 2 j +2 4 2 j +4 1 2 3 1 2 3 4 1 2 3 4 constants you found in problem 8. Assuming these results, determine, with proof, the value of A . 0 Page 2 of 3 Geometry [90]
解析
- [ 20 ] Once it has been demonstrated that lim p (0) exists and is greater than 0, it follows that n n →∞ ∞ ∑ lim p ( k ) exists and is greater than 0 for all even positive integers k and that A = 1. It also n 2 k n →∞ k =0 follows that A = a A + a A + a A , A = b A + b A + b A + b A , and A = c A + c A + 0 1 0 2 2 3 4 2 1 0 2 2 3 4 4 6 2 j 1 2 j − 2 2 2 j c A + c A for all positive integers j ≥ 2, where a , a , a , b , b , b , b , and c , c , c , c are the 3 2 j +2 4 2 j +4 1 2 3 1 2 3 4 1 2 3 4 constants you found in problem 8. Assuming these results, determine, with proof, the value of A . 0 Solution: By our recurrence relations, 1 1 1 A = A + A 0 2 4 4 2 8 5 1 3 1 A = A + A + A 2 0 4 6 8 4 8 8 and 5 1 3 1 A = A + A + A 2 k 2 k − 2 2 k +2 2 k +4 8 8 8 8 for all k ≥ 2. So the terms A ( k ≥ 1) satisfy a linear recurrence with characteristic equation 2 k √ 3 2 x + 3 x + 1 = 5 x . The roots of the characteristic equation are 1 and − 2 ± 5, so for k ≥ 2, √ √ k k A = c + c ( − 2 + 5) + c ( − 2 − 5) . But clearly, lim A = 0, so c = c = 0. Thus for k ≥ 2, 2 k 1 2 3 2 k 1 3 k →∞ √ √ k k − 2 we are left with A = c ( − 2 + 5) = A ( − 2 + 5) . 2 k 2 4 ∞ ∞ ∑ ∑ √ A 4 j √ Now, since A = 1, we get 1 = A + A + A ( 5 − 2) = A + A + = 2 k 0 2 4 0 2 1 − ( 5 − 2) j =0 k =0 √ 3 + 5 A + A + A . 0 2 4 4 We now have the following equations. √ 3 + 5 1 = A + A + A 0 2 4 4 0 = 2 A − 4 A − A 0 2 4 √ 0 = 2 A − 5 A + 3 A + A = 2 A − 5 A + (1 + 5) A 0 2 4 6 0 2 4 √ 5 − 1 We have three equations with three unknowns. Solving this linear system gives A = . 0 2 √ 5 − 1 1 Remark: The fact that A = > means that for arbitrarily large n , the player wins more often 0 2 2 than they lose, so the player is at an advantage. In addition the final answer is the reciprocal of the golden ratio, which is simply beautiful. The probabilistic experiment explored in this problem is a type of random walk. A random walk is an n infinite set of moves in some set (usually the R lattice but sometimes weird shapes or even fractals) Team Round A where each move is determined by a random variable. The most basic random walk is a walk on the 1 real line, where the walker starts at 0, and at every move has probability of moving one unit to the 2 1 left, and probability of moving one unit to the right. 2 The random walk explored in this problem is what is known as a ’biased’ random walk, where the probabilities of movement are asymmetric, and weighted towards a certain direction or outcome. In this example the choice of the side of 1 out of every 4 coins biases the walk towards the origin. An interesting inquiry for the reader to ponder is, what is the value of A if the game is played with 6 0 coins flipped each turn, or 8, or 2 m . If the limits A exist, they will satisfy a linear recurrence with 2 k ( ) 2 m − 1 x + 1 m − 1 characteristic equation = x , as is evident from this problem, where we solved the 2 m = 2 case. ∞ ∑ We now give proofs that A exists for all even k , and that A = 1 k 2 k k =0 First note that we can use the inductive argument in problem 9a to prove the stronger bound p (0) ≥ n √ √ 2+ 5 p (2) and p (2 k ) ≥ (2 + 5) p (2 k + 2) for all k ≥ 1. n n n 2 Now, 1 3 3 1 p (0) + p (2) = p (0) + p (2) + p (4) n +2 n +1 n +1 n +1 n +1 4 4 4 8 3 43 27 9 1 = p (0) + p (2) + p (4) + p (6) + p (8) n n n n n 4 64 64 64 64 11 19 9 1 = p (0) + p (2) + p (4) + p (6) + p (8) n +1 n n n n 64 64 64 64 1 5 19 9 1 = p (0) + p (2) − p (2) + p (4) + p (6) + p (8) n +1 n n n n n 4 64 64 64 64 1 ≤ p (0) + p (2) n +1 n 4 So p (0) + p (2) is a non-increasing sequence that is bounded below, so it converges to a limit, call n +1 n it A + A . Now A = − lim p (0) + lim ( p (0) + p (2)) = lim p (2). 0 2 2 n +1 n +1 n n n →∞ n →∞ n →∞ So lim p (2) exists. It follows from our recursions that A exists for all k . Since p (2 k ) ≥ 0 for all n 2 k n n →∞ k , it follows that all the A are non-negative. i ∞ ∑ Now we must show that A = 1. This is not immediately clear because, while a finite sum of 2 k k =0 limits of sequences equals the limit of the finite sum of the sequences, the sum of the limits does not necessarily equal the limit of the sum if it is an infinite sum. N ∑ Now it follows from part 8a, that for any > 0 there exists N such that p (2 k ) > 1 − for all n . n 2 k =0 N ∞ ∑ ∑ So A ≥ 1 − > 1 − . Since A ≥ 0 for all k , A ≥ 1. 2 k 2 k 2 k 2 k =0 k =0 j ∞ ∑ ∑ Now if A is greater than 1, or diverges, then there exists a pair j and > 0 such that A = 2 k 2 k k =0 k =0 j j ∑ ∑ 1 + . But, p (2 k ) ≤ 1 for all n , so A ≤ 1, contradiction. n 2 k k =0 k =0 ∞ ∑ So A = 1. 2 k k =0 Team Round A Geometry [90]