HMMT 二月 2015 · 代数 · 第 9 题

英文解析

9. Let N = 30 . Find the number of ordered 4-tuples of integers ( A, B, C, D ) ∈ { 1 , 2 , . . . , N } (not
   3 2
   necessarily distinct) such that for every integer n , An + Bn + 2 Cn + D is divisible by N .
   ( ) ( ) ( ) ( ) ( ) ( ) ( )
   n n n n n n n
   0 1 2 3
   Answer: 24 Note that n = , n = , n = 2 + , n = 6 + 6 + (generally see
   0 1 2 1 3 2 1
   http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind ). Thus the polynomialrewrites as
   ( ) ( ) ( ) ( )
   n n n n
   6 A + (6 A + 2 B ) + ( A + B + 2 C ) + D ,
   3 2 1 0
   5 − 11
   This is more explicit than necessary. By the same reasoning as in the previous paragraph, we can abstractly count 1 +4
   quadratic residues modulo x ± 2 (irreducible polynomials in F [ x ]) each (and then multiply/square to get the answer for x + 1).22
   Algebra 5
   which by the classification of integer-valued polynomials is divisible by N always if and only if 6 A, 6 A +
   2 B, A + B + 2 C, D are always divisible by N .
   We can eliminate B and (trivially) D from the system: it’s equivalent to the system 6 A ≡ 0 (mod N ),
   4 A − 4 C ≡ 0 (mod N ), B ≡ − A − 2 C (mod N ), D ≡ 0 (mod N ). So we want 1 times the number of 2
   ( A, C ) with A ≡ 0 (mod N/ 6), C ≡ A (mod N/ 4). So there are N/ ( N/ 6) = 6 choices for A , and thengiven such a choice of A there are N/ ( N/ 4) = 4 choices for C . So we have 6 · 4 · 1 = 24 solutions total.2