HMMT 二月 2008 · TEAM2 赛 · 第 4 题

英文解析

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 np ( x ) = a ( x ⊕ r ) ( x ⊕ r ) · · · ( x ⊕ r )
   n 1 2 nfor all x .
   Solution: Again, we havep ( x ) = min { a + kx } .
   0 ≤ k ≤ nk
   So the graph of y = p ( x ) can be drawn as follows: first, draw all the lines y = a + kx ,
   k = 0 , 1 , . . . , n , then trace out the lowest broken line, which then is the graph of y = p ( x ).k
   So p ( x ) is piecewise linear and continuous, and has slopes from the set { 0 , 1 , 2 , . . . , n } . Weknow 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 rkdenote the x -coordinate of the leftmost kink such that the slope of the graph is less than kto the right of this kink. Then, r ≤ r ≤ · · · ≤ r , and for r ≤ x ≤ r , the graph ofn n − 1 1 k − 1 kp is linear with slope k . Note that is if possible that r = r , if no segment of p has slopek − 1 kk . Also, since a 6 = ∞ , the leftmost piece of p ( x ) must have slope n , and thus r exists, andn nthus all r exist.
   Now, compare p ( x ) withiq ( 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 ≥ rn 1
   k − 1 kthe slope of q is 0. So q is piecewise linear, and of course it is continuous. It follows that thegraph of q coincides with that of p up to a translation. By taking any x < r , we see thatnq ( x ) = a + nx = p ( x ), we see that the graphs of p and q coincide, and thus they must benthe same function.
   Juggling [ 125 ]2
   A juggling sequence of length n is a sequence j ( · ) of n nonnegative integers, usually written as astringj (0) j (1) . . . j ( n − 1)
   such that the mapping f : Z → Z defined byf ( 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 permutation induces b infinite orbits on the set of integers. Equivalently, b is the maximum number suchthat 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 iare all infinite and mutually disjoint (i.e. non-overlapping) for i = 1 , 2 , . . . , b . (This definition willbecome 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 handat time f ( t ) = t + j ( t ). Then, the juggling pattern presents a simplified model of how balls arejuggled (for instance, we ignore information such as which hand we use to toss the ball). A throwheight of 0 (i.e., j ( t ) = 0 and f ( t ) = t ) represents that no thrown takes place at time t , which couldcorrespond to an empty hand. Then, b is simply the minimum number of balls needed to carry outthe juggling.
   The following graphical representation may be helpful to you. On a horizontal line, an curve isdrawn from t to f ( t ). For instance, the following diagram depicts the juggling sequence 441 (or thejuggling sequences 414 and 144). Then b is simply the number of contiguous “paths” drawn, whichis 3 in this case.
   4 4 1 4 4 1 4 4 1 4 4
   Figure 1: Juggling diagram of 441.