HMMT 二月 2010 · 代数 · 第 8 题
HMMT February 2010 — Algebra — Problem 8
题目详情
- [ 6 ] How many polynomials of degree exactly 5 with real coefficients send the set { 1 , 2 , 3 , 4 , 5 , 6 } to a permutation of itself? n
解析
- [ 6 ] How many polynomials of degree exactly 5 with real coefficients send the set { 1 , 2 , 3 , 4 , 5 , 6 } to a permutation of itself? 1 Answer: 714 For every permutation σ of { 1 , 2 , 3 , 4 , 5 , 6 } , Lagrange Interpolation gives a polynomial of degree at most 5 with p ( x ) = σ ( x ) for every x = 1 , 2 , 3 , 4 , 5 , 6. Additionally, this polynomial is unique: assume that there exist two polynomials p, q of degree ≤ 5 such that they map { 1 , 2 , 3 , 4 , 5 , 6 } to the same permutation. Then p − q is a nonzero polynomial of degree ≤ 5 with 6 distinct roots, a contradiction. Thus an upper bound for the answer is 6! = 720 polynomials. However, not every polynomial obtained by Lagrange interpolation is of degree 5 (for example, p ( x ) = 2 x ). We can count the number of invalid polynomials using finite differences. A polynomial has degree less than 5 if and only if the sequence of 5th finite differences is 0. The 5th finite difference of p (1) , p (2) , p (3) , p (4) , p (5) , p (6) is p (1) − 5 p (2) + 10 p (3) − 10 p (4) + 5 p (5) − p (6); thus we want to solve p (1) − 5 p (2)+10 p (3) − 10 p (4)+5 p (5) − p (6) = 0 with { p (1) , p (2) , p (3) , p (4) , p (5) , p (6) } = { 1 , 2 , 3 , 4 , 5 , 6 } . Taking the above equation modulo 5, we get p (1) = p (6) (mod 5) = ⇒ { p (1) , p (6) } = { 1 , 6 } . Note that 1 − 5 p (2)+10 p (3) − 10 p (4)+5 p (5) − 6 = 0 if and only if 6 − 5 p (5)+10 p (4) − 10 p (3)+5 p (2) − 1 = 0, so we may assume that p (1) = 1 and double our result later. Then we have { p (2) , p (3) , p (4) , p (5) } = { 2 , 3 , 4 , 5 } and − p (2) + 2 p (3) − 2 p (4) + p (5) = 1 . The above equation taken modulo 2 implies that p (2) , p (5) are of opposite parity, so p (3) , p (4) are of opposite parity. We do casework on { p (2) , p (5) } : (a) p (2) = 2 , p (5) = 3; 2 p (3) − 2 p (4) = 0 is a contradiction (b) p (2) = 2 , p (5) = 5; 2 p (3) − 2 p (4) = − 2 = ⇒ p (3) − p (4) = − 1 = ⇒ p (3) = 3 , p (4) = 4 (c) p (2) = 3 , p (5) = 2; 2 p (3) − 2 p (4) = − 2 = ⇒ p (3) − p (4) = − 1 = ⇒ p (3) = 4 , p (4) = 5 (d) p (2) = 3 , p (5) = 4; 2 p (3) − 2 p (4) = 0 is a contradiction (e) p (2) = 4 , p (5) = 3; 2 p (3) − 2 p (4) = 2 = ⇒ p (3) − p (4) = 1 but { p (3) , p (4) } = { 2 , 5 } , contradiction (f) p (2) = 4 , p (5) = 5; 2 p (3) − 2 p (4) = 0 is a contradiction (g) p (2) = 5 , p (5) = 2; 2 p (3) − 2 p (4) = 4 = ⇒ p (3) − p (4) = 2, contradiction (h) p (2) = 5 , p (5) = 4; 2 p (3) − 2 p (4) = 2 = ⇒ p (3) − p (4) = 1 = ⇒ p (3) = 3 , p (4) = 2 Hence there are a total of 720 − 2(3) = 714 polynomials. 1 See http://en.wikipedia.org/wiki/Lagrange_interpolation . 2 See http://www.artofproblemsolving.com/Forum/weblog_entry.php?p=1263378 . Algebra Subject Test n