HMMT 二月 2008 · TEAM2 赛 · 第 3 题

英文解析

3. [ 35 ] By a tropical polynomial we mean a function of the formn n − 1
   p ( x ) = a x ⊕ a x ⊕ · · · ⊕ a x ⊕ a ,
   n n − 1 1 0
   where exponentiation is as defined in the previous problem.
   Let p be a tropical polynomial. Prove that
   ( )
   x + y p ( x ) + p ( y )
   p ≥
   2 2
   for all x, y ∈ R ∪ {∞} . (This means that all tropical polynomials are concave.)
   Solution: First, note that for any x , . . . , x , y , . . . , y , we have
   1 n 1 nmin { x + y , x + y , . . . , x + y } ≥ min { x , x , . . . , x } + min { y , y , . . . , y } .
   1 1 2 2 n n 1 2 n 1 2 n
   Indeed, suppose that x + y = min { x + y } , then x ≥ min x and y ≥ min y , and som m i i i m i i m i imin { x + y } = x + y ≥ min x + min y .
   i i i m m i i i i
   Now, let us write a tropical polynomial in a more familiar notation. We havep ( x ) = min { a + kx } .
   0 ≤ k ≤ nk
   So 1
   ( ) { ( )}
   x + y x + yp = min a + k
   2 0 ≤ k ≤ n 2 k = min { ( a + kx ) + ( a + ky ) }1
   k k
   2 0 ≤ k ≤ n
   ( )
   ≥ min { a + kx } + min { a + ky }1
   k k
   2 0 ≤ k ≤ n 0 ≤ k ≤ n = ( p ( x ) + p ( y )) .1 2