HMMT 二月 2010 · TEAM2 赛 · 第 9 题
HMMT February 2010 — TEAM2 Round — Problem 9
题目详情
- [ 35 ] Let S be the set of ordered pairs of integers ( x, y ) with 1 ≤ x ≤ 5 and 1 ≤ y ≤ 3. How many subsets 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 that a is allowed to be 0).
解析
- [ 35 ] Let S be the set of ordered pairs of integers ( x, y ) with 1 ≤ x ≤ 5 and 1 ≤ y ≤ 3. How many subsets 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 that a is allowed to be 0). Answer: 796 We observe that R must contain at most 1 point from each column of S , because no function can contain more than 1 point with the same x -coordinate. Therefore, | R | ≤ 5 ( | R | denotes the number of elements of R ). Note that 4 points determine a cubic, so if R is any subset of points in 5 distinct columns and | R | ≤ 4, then R has the desired property. There are 4 ways to choose at most 1 Team Round B 5 point from each column and 3 ways to choose exactly 1 point from each column. There are therefore 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 unique polynomial p of degree less than 5 going through 5 specified points, and this polynomial is of degree less 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 solutions to 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 is only 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 two solutions 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 only be 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) can only 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 possible subset 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 of degree less than 4. Hence there are 781 + 15 = 796 possible subsets total.