HMMT 二月 2010 · TEAM2 赛 · 第 9 题

英文解析

9. [ 35 ] Let S be the set of ordered pairs of integers ( x, y ) with 1 ≤ x ≤ 5 and 1 ≤ y ≤ 3. How manysubsets R of S have the property that all the points of R lie on the graph of a single cubic? A cubic is
   3 2
   a polynomial of the form y = ax + bx + cx + d , where a , b , c , and d are real numbers (meaning thata is allowed to be 0).
   Answer: 796 We observe that R must contain at most 1 point from each column of S , because nofunction can contain more than 1 point with the same x -coordinate. Therefore, | R | ≤ 5 ( | R | denotesthe number of elements of R ). Note that 4 points determine a cubic, so if R is any subset of points indistinct columns and | R | ≤ 4, then R has the desired property. There are 4 ways to choose at most 15
   Team Round Bpoint from each column and 3 ways to choose exactly 1 point from each column. There are therefore 5
   5 5
   4 − 3 = 781 subsets R of S such that | R | ≤ 4 and all points of R lie in distinct columns. As noted,
   these sets all automatically have the desired property.
   Now we consider all sets R of size 5. As before, each point in R must come from a different column.
   Let us shift our origin to (3 , 2), and let p be the polynomial containing all 5 points of R . Then
   R = { ( − 2 , p ( − 2)) , ( − 1 , p ( − 1)) , (0 , p (0)) , (1 , p (1)) , (2 , p (2)) } .
   3 4
   By the method of finite differences , or alternately by Lagrange Interpolation , there is a uniquepolynomial p of degree less than 5 going through 5 specified points, and this polynomial is of degreeless than 4 if and only if p ( − 2) − 4 p ( − 1) + 6 p (0) − 4 p (1) + p (2) = 0.
   Then p ( − 2) + p (2) + 6 p (0) = 4( p ( − 1) + p (1)), where p ( − 2) + p (2) ∈ {− 2 − 1 , 0 , 1 , 2 } , p ( − 1) + p (1) ∈
   {− 2 , − 1 , 0 , 1 , 2 } , and p (0) ∈ {− 1 , 0 , 1 } . We know that 6 p (0) and 4( p ( − 1) + p (1)) are necessarily even,
   thus we must have p ( − 2) + p (2) ∈ {− 2 , 0 , 2 } in order for the equation to be satisfied.
   Let ( a, b, c ) = ( p ( − 2) + p (2) , 6 p (0) , 4( p ( − 1) + p (1))). The possible values of ( a, b, c ) that are solutionsto a + b = c are then { ( − 2 , − 6 , − 8) , ( − 2 , 6 , 4) , (0 , 0 , 0) , (2 , − 6 , − 4) , (2 , 6 , 8) } .
   If ( a, b, c ) = ( − 2 , − 6 , − 8), then we need p ( − 2) + p (2) = − 2, p (0) = − 1, p ( − 1) + p (1) = − 2. There isonly 1 possible solution to each of these equations: ( p ( − 2) , p (2)) = ( − 1 , − 1) for the first one, p (0) = − 1
   for the second, and ( p (1)) = ( − 1 , − 1) for the third. Hence there is 1 possible subset R for the case
   ( a, b, c ) = ( − 2 , − 6 , − 8).
   If ( a, b, c ) = ( − 2 , 6 , 4), then there is again 1 possible solution to p ( − 2) + p (2) = 1. There are twosolutions to p ( − 1) + p (1) = 1: ( p ( − 1) , p (1)) = (0 , 1) , (1 , 0). Also, p (0) can only be 1, so there are 2
   possible subsets for this case.
   If ( a, b, c ) = (0 , 0 , 0), then there there are 3 possible solutions to p ( − 2) + p (2) = 0: ( p ( − 2) , p (2)) =
   ( − 1 , 1) , (0 , 0) , (1 , − 1). Similarly, there are 3 possible solutions to p ( − 1) + p (1) = 0. Also, p (0) can onlybe 0, so there are 9 possible subsets for this case.
   If ( a, b, c ) = (2 , − 6 , − 4), then there is 1 possible solution to p ( − 2) + p (2) = 2: ( p ( − 2) , p (2)) = (1 , 1).
   There are 2 possible solutions to p ( − 1) + p (1) = − 1: ( p ( − 1) , p (1)) = (0 , − 1) , ( − 1 , 0). Also, p (0) canonly be -1, so there are 2 possible subsets for this case.
   If ( a, b, c ) = (2 , 6 , 8), then there is 1 possible solution to p ( − 2) + p (2) = 2, as shown above. There is
   1 solution to p ( − 1) + p (1) = 2: ( p ( − 1) , p (1)) = (1 , 1). Also, p (0) can only be 1, so there is 1 possiblesubset for this case.
   Then there are 1 + 2 + 9 + 2 + 1 = 15 total possible subsets of size 5 that can be fit to a polynomial ofdegree less than 4. Hence there are 781 + 15 = 796 possible subsets total.