HMMT November, 2014

Number theory Difficulty 4.7 AIME Find the answer United States

Problem:

For any positive integer $x$ , define $\operatorname{Accident}(x)$ to be the set of ordered pairs $(s, t)$ with $s \in \{0,2,4,5,7,9,11\}$ and $t \in \{1,3,6,8,10\}$ such that $x+s-t$ is divisible by $12$ . For any nonnegative integer $i$ , let $a_{i}$ denote the number of $x \in \{0,1, \ldots, 11\}$ for which $|\operatorname{Accident}(x)|=i$ . Find
$a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+a_{4}^{2}+a_{5}^{2}$

Your answer

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

Solution

Solution:

Answer: 26

Modulo twelve, the first set turns out to be $\{-1 \cdot 7, 0 \cdot 7, \ldots, 5 \cdot 7\}$ and the second set turns out to be $\{6 \cdot 7, \ldots, 10 \cdot 7\}$ . We can eliminate the factor of $7$ and shift to reduce the problem to $s \in \{0,1, \ldots, 6\}$ and $t \in \{7, \ldots, 11\}$ . With this we can easily compute $\left(a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}\right) = (1,2,2,2,2,3)$ . Therefore, the answer is $26$ .

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.