HMMT 二月 2008 · TEAM2 赛 · 第 4 题
HMMT February 2008 — TEAM2 Round — Problem 4
题目详情
- [ 40 ] (Fundamental Theorem of Algebra) Let p be a tropical polynomial: n n − 1 p ( x ) = a x ⊕ a x ⊕ · · · ⊕ a x ⊕ a , a 6 = ∞ n n − 1 1 0 n Prove that we can find r , r , . . . , r ∈ R ∪ {∞} so that 1 2 n p ( x ) = a ( x ⊕ r ) ( x ⊕ r ) · · · ( x ⊕ r ) n 1 2 n for all x . Juggling [ 125 ] A juggling sequence of length n is a sequence j ( · ) of n nonnegative integers, usually written as a string j (0) j (1) . . . j ( n − 1) such that the mapping f : Z → Z defined by f ( t ) = t + j ( t ) 1 is a permutation of the integers. Here t denotes the remainder of t when divided by n . In this case, we say that f is the corresponding juggling pattern . For a juggling pattern f (or its corresponding juggling sequence), we say that it has b balls if the per- mutation induces b infinite orbits on the set of integers. Equivalently, b is the maximum number such that we can find a set of b integers { t , t , . . . , t } so that the sets { t , f ( t ) , f ( f ( t )) , f ( f ( f ( t ))) , . . . } 1 2 b i i i i are all infinite and mutually disjoint (i.e. non-overlapping) for i = 1 , 2 , . . . , b . (This definition will become clear in a second.) Now is probably a good time to pause and think about what all this has to do with juggling. Imagine that we are juggling a number of balls, and at time t , we toss a ball from our hand up to a height j ( t ). This ball stays up in the air for j ( t ) units of time, so that it comes back to our hand at time f ( t ) = t + j ( t ). Then, the juggling pattern presents a simplified model of how balls are juggled (for instance, we ignore information such as which hand we use to toss the ball). A throw height of 0 (i.e., j ( t ) = 0 and f ( t ) = t ) represents that no thrown takes place at time t , which could correspond to an empty hand. Then, b is simply the minimum number of balls needed to carry out the juggling. The following graphical representation may be helpful to you. On a horizontal line, an curve is drawn from t to f ( t ). For instance, the following diagram depicts the juggling sequence 441 (or the juggling sequences 414 and 144). Then b is simply the number of contiguous “paths” drawn, which is 3 in this case. 4 4 1 4 4 1 4 4 1 4 4 Figure 1: Juggling diagram of 441.
解析
- [ 40 ] (Fundamental Theorem of Algebra) Let p be a tropical polynomial: n n − 1 p ( x ) = a x ⊕ a x ⊕ · · · ⊕ a x ⊕ a , a 6 = ∞ n n − 1 1 0 n Prove that we can find r , r , . . . , r ∈ R ∪ {∞} so that 1 2 n p ( x ) = a ( x ⊕ r ) ( x ⊕ r ) · · · ( x ⊕ r ) n 1 2 n for all x . Solution: Again, we have p ( x ) = min { a + kx } . k 0 ≤ k ≤ n So the graph of y = p ( x ) can be drawn as follows: first, draw all the lines y = a + kx , k k = 0 , 1 , . . . , n , then trace out the lowest broken line, which then is the graph of y = p ( x ). So p ( x ) is piecewise linear and continuous, and has slopes from the set { 0 , 1 , 2 , . . . , n } . We know from the previous problem that p ( x ) is concave, and so its slope must be decreasing (this can also be observed simply from the drawing of the graph of y = p ( x )). Then, let r k denote the x -coordinate of the leftmost kink such that the slope of the graph is less than k to the right of this kink. Then, r ≤ r ≤ · · · ≤ r , and for r ≤ x ≤ r , the graph of n n − 1 1 k − 1 k p is linear with slope k . Note that is if possible that r = r , if no segment of p has slope k − 1 k k . Also, since a 6 = ∞ , the leftmost piece of p ( x ) must have slope n , and thus r exists, and n n thus all r exist. i Now, compare p ( x ) with q ( x ) = a ( x ⊕ r ) ( x ⊕ r ) · · · ( x ⊕ r ) n 1 2 n = a + min( x, r ) + min( x, r ) + · · · + min( x, r ) . n 1 2 n For r ≤ x ≤ r , the slope of q ( x ) is k , and for x ≤ r the slope of q is n and for x ≥ r n 1 k − 1 k the slope of q is 0. So q is piecewise linear, and of course it is continuous. It follows that the graph of q coincides with that of p up to a translation. By taking any x < r , we see that n q ( x ) = a + nx = p ( x ), we see that the graphs of p and q coincide, and thus they must be n the same function. 2 Juggling [ 125 ] A juggling sequence of length n is a sequence j ( · ) of n nonnegative integers, usually written as a string j (0) j (1) . . . j ( n − 1) such that the mapping f : Z → Z defined by f ( t ) = t + j ( t ) is a permutation of the integers. Here t denotes the remainder of t when divided by n . In this case, we say that f is the corresponding juggling pattern . For a juggling pattern f (or its corresponding juggling sequence), we say that it has b balls if the per- mutation induces b infinite orbits on the set of integers. Equivalently, b is the maximum number such that we can find a set of b integers { t , t , . . . , t } so that the sets { t , f ( t ) , f ( f ( t )) , f ( f ( f ( t ))) , . . . } 1 2 b i i i i are all infinite and mutually disjoint (i.e. non-overlapping) for i = 1 , 2 , . . . , b . (This definition will become clear in a second.) Now is probably a good time to pause and think about what all this has to do with juggling. Imagine that we are juggling a number of balls, and at time t , we toss a ball from our hand up to a height j ( t ). This ball stays up in the air for j ( t ) units of time, so that it comes back to our hand at time f ( t ) = t + j ( t ). Then, the juggling pattern presents a simplified model of how balls are juggled (for instance, we ignore information such as which hand we use to toss the ball). A throw height of 0 (i.e., j ( t ) = 0 and f ( t ) = t ) represents that no thrown takes place at time t , which could correspond to an empty hand. Then, b is simply the minimum number of balls needed to carry out the juggling. The following graphical representation may be helpful to you. On a horizontal line, an curve is drawn from t to f ( t ). For instance, the following diagram depicts the juggling sequence 441 (or the juggling sequences 414 and 144). Then b is simply the number of contiguous “paths” drawn, which is 3 in this case. 4 4 1 4 4 1 4 4 1 4 4 Figure 1: Juggling diagram of 441.