HMMT 二月 2008 · TEAM2 赛 · 第 3 题

HMMT February 2008 — TEAM2 Round — Problem 3

[ 35 ] By a tropical polynomial we mean a function of the form n 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.)

解析

[ 35 ] By a tropical polynomial we mean a function of the form n 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 n min { 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 so m m i i i m i i m i i min { 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 have p ( x ) = min { a + kx } . k 0 ≤ k ≤ n 1 So ( ) { ( )} x + y x + y p = min a + k k 2 0 ≤ k ≤ n 2 1 = min { ( a + kx ) + ( a + ky ) } k k 2 0 ≤ k ≤ n ( ) 1 ≥ min { a + kx } + min { a + ky } k k 2 0 ≤ k ≤ n 0 ≤ k ≤ n 1 = ( p ( x ) + p ( y )) . 2