Maths Olympiad Prep

Library / /152 of 348

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. Spacing and $ signs are ignored.

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++2012x20120(mod2012)x_{1}+2 x_{2}+\ldots+2012 x_{2012} \equiv 0(\bmod 2012) or x1(2x2++2012x2012)(mod2012)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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.