HMMT 二月 2012 · 代数 · 第 10 题
HMMT February 2012 — Algebra — Problem 10
题目详情
- Suppose that there are 16 variables { a } , each of which may be 0 or 1. For how many settings i,j 0 ≤ i,j ≤ 3 of the variables a do there exist positive reals c such that the polynomial i,j i,j ∑ i j f ( x, y ) = a c x y i,j i,j 0 ≤ i,j ≤ 3 ( x, y ∈ R ) is bounded below? th 15 Annual Harvard-MIT Mathematics Tournament Saturday 11 February 2012 Algebra Test Name Team ID# School Team
Score:
解析
- Suppose that there are 16 variables { a } , each of which may be 0 or 1. For how many settings i,j 0 ≤ i,j ≤ 3 of the variables a do there exist positive reals c such that the polynomial i,j i,j ∑ i j f ( x, y ) = a c x y i,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) } . Let i,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 + bj f ( − 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 infinitely i,j ′ ′ ai + bj ′ ′ ′ ′ large, as there is a − c t term, with ai + bj > 0, and all other terms have smaller powers of i ,j t . 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 k coordinates of v , respectively. k ∑ ∑ n n ′ Since w ∈ C ( S ), there exist nonnegative constants λ , λ , . . . , λ such that λ = 1 and λ v = 1 2 n k k k k =1 k =1 w . (Here, we are treating the ordered pairs as vectors.) Then, by weighted AM-GM, we have n ∑ ′ ′ i j i j k k λ | x | | y | ≥ | x | | y | . k k =1 ′ ′ Let c be the λ -value associated with (0 , 0). Then by picking c = λ and c = 1, we find that i ,j k i ,j k k p ( 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. There i,j are 8 such possible convex hulls: the point (0 , 0) only, 3 lines, 3 triangles, and the square. The point has 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