HMMT 二月 2015 · 代数 · 第 9 题

HMMT February 2015 — Algebra — Problem 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 .

解析

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 polynomial rewrites as ( ) ( ) ( ) ( ) n n n n 6 A + (6 A + 2 B ) + ( A + B + 2 C ) + D , 3 2 1 0 1 5 − 1 4 This is more explicit than necessary. By the same reasoning as in the previous paragraph, we can abstractly count 1 + 2 2 quadratic residues modulo x ± 2 (irreducible polynomials in F [ x ]) each (and then multiply/square to get the answer for x + 1). 5 Algebra 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 ), 2 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 ( A, C ) with A ≡ 0 (mod N/ 6), C ≡ A (mod N/ 4). So there are N/ ( N/ 6) = 6 choices for A , and then 2 given such a choice of A there are N/ ( N/ 4) = 4 choices for C . So we have 6 · 4 · 1 = 24 solutions total.