HMMT 二月 2012 · 代数 · 第 10 题

英文解析

10. Suppose that there are 16 variables { a } , each of which may be 0 or 1. For how many settingsi,j 0 ≤ i,j ≤ 3
    of the variables a do there exist positive reals c such that the polynomiali,j i,j
    ∑
    i jf ( x, y ) = a c x yi,j i,j
    0 ≤ i,j ≤ 3
    Algebra Test
    ( x, y ∈ R ) is bounded below?
    ′
    Answer: 126 For some choices of the a , let S = { ( i, j ) | a = 1 } , and let S = S ∪ { (0 , 0) } . Leti,j i,j
    ′ ′
    C ( S ) denote the convex hull of S . We claim that there exist the problem conditions are satisfied
    (there exist positive coefficients for the terms so that the polynomial is bounded below) if and only if
    ′
    the vertices of C ( S ) all have both coordinates even.
    ′ ′ ′
    For one direction, suppose that C ( S ) has a vertex v = ( i , j ) with at least one odd coordinate; WLOG,
    ′ ′
    suppose it is i . Since v is a vertex, it maximizes some objective function ai + bj over C ( S ) uniquely,
    ′ ′ ′ ′
    and thus also over S . Since (0 , 0) ∈ S , we must have ai + bj > 0. Now consider plugging in a b
    ( x, y ) = ( − t , t ) ( t > 0) into f . This gives the value
    ∑
    a b i ai + bjf ( − t , t ) = ( − 1) c t .
    i,j
    ( i,j ) ∈ S
    But no matter what positive c we choose, this expression is not bounded below as t grows infinitelyi,j
    ′ ′
    ai + bj ′ ′
    ′ ′
    large, as there is a − c t term, with ai + bj > 0, and all other terms have smaller powers ofi ,jt . So the polynomial cannot be bounded below.
    ′ ′
    For the other direction, suppose the vertices of C ( S ) all have both coordinates even. If all points in S
    ′
    are vertices of C ( S ), then the polynomial is a sum of squares, so it is bounded below. Otherwise, we
    ′ ′
    assume that some points in S are not vertices of C ( S ). It suffices to consider the case where there is
    ′ ′ ′ ′
    exactly one such point. Call this point w = ( i , j ). Let V ( S ) denote the set of the vertices of C ( S ),
    ′ ′
    and let n = | V ( S ) | . Enumerate the points of V ( S ) as v , v , . . . , v . Let i , j denote the i and j
    1 2 n k kcoordinates of v , respectively.
    ∑ ∑kn n
    ′
    Since w ∈ C ( S ), there exist nonnegative constants λ , λ , . . . , λ such that λ = 1 and λ v =
    1 2 n k k kk =1 k =1
    w . (Here, we are treating the ordered pairs as vectors.) Then, by weighted AM-GM, we haven
    ∑
    ′ ′
    i j i jk kλ | x | | y | ≥ | x | | y | .
    k =1 k
    ′ ′
    Let c be the λ -value associated with (0 , 0). Then by picking c = λ and c = 1, we find thati ,j k i ,jk kp ( x, y ) ≥ − c for all x, y , as desired.
    ′
    We now find all possible convex hulls C ( S ) (with vertices chosen from (0 , 0) , (0 , 2) , (2 , 0), and (2 , 2)),
    and for each convex hull, determine how many possible settings of a give that convex hull. Therei,jare 8 such possible convex hulls: the point (0 , 0) only, 3 lines, 3 triangles, and the square. The pointhas 2 possible choices, each line has 4 possible choices, each triangle has 16 possible choices, and the square has 64 possible choices, giving 2 + 3 · 4 + 3 · 16 + 64 = 126 total choices.
    Algebra Test