Competition problem — Combinatorics

Library / /42 of 348

Combinatorics Difficulty 4.6 AIME Find the answer

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

Solution

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 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,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.