Let be an odd integer, and let denote the number of quadruples of distinct integers with for all such that divides . There is a polynomial such that for all odd integers . What is ?
Pick one
Solution
Let denote the number of quadruples of distinct residue classes modulo such that . Because the total number of quadruples of distinct residue classes is , it follows that
Note that the pairing provides a one-to-one correspondence between quadruples of distinct residue classes that sum to and quadruples of distinct residue classes that sum to . Hence , so
Now because is odd, so the numbers form a complete residue system modulo . Thus the values are all equal. From the displayed summation above it follows that
for all . Because , it follows that the required polynomial is , and .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.