Maths Olympiad Prep

Library / HMMT November /213 of 672

HMMT November

Algebra Difficulty 4.9 AIME Find the answer

Find the number of ordered 2012-tuples of integers (x1,x2,…,x2012)\left(x_{1}, x_{2}, \ldots, x_{2012}\right), with each integer between 0 and 2011 inclusive, such that the sum x1+2x2+3x3+⋯+2012x2012x_{1}+2 x_{2}+3 x_{3}+\cdots+2012 x_{2012} is divisible by 2012.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We claim that for any choice of x2,x3,…,x2012x_{2}, x_{3}, \ldots, x_{2012}, there is exactly one possible value of x1x_{1} satisfying the condition. We have x1+2x2+…+2012x2012≡0( mod 2012)x_{1}+2 x_{2}+\ldots+2012 x_{2012} \equiv 0(\bmod 2012) or x1≡−(2x2+…+2012x2012)( mod 2012)x_{1} \equiv -\left(2 x_{2}+\ldots+2012 x_{2012}\right)(\bmod 2012). Indeed, we see that the right hand side is always an integer between 0 and 2011, so x1x_{1} must equal this number. Now, there are 2012 choices for each of the 2011 variables x2,…,x2012x_{2}, \ldots, x_{2012}, and each of the 201220112012^{2011} possible combinations gives exactly one valid solution, so the total number of 2012-tuples is 201220112012^{2011}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.