Library / /65 of 133

, 2015

Number theory Difficulty 5.6 AIME, harder Prove it Saudi Arabia

How many sequences of integers
$1 \leq a_{1} \leq a_{2} \leq \ldots \leq a_{11} \leq 2015$
that satisfy $a_{i} \equiv i^{2} (\bmod\ 12)$ for all $1 \leq i \leq 11$ are there?

Solution

Let $r_{i}$ be the remainder when $i^{2}$ is divided by $12$ , and $a_{i} = 12 k_{i} + r_{i}$ for some nonnegative integer $k_{i}$ , when $1 \leq i \leq 11$ . From the following table showing the values of $r_{i}$

$i$	1	2	3	4	5	6	7	8	9	10	11
$r_{i}$	1	4	9	4	1	0	1	4	9	4	1

we deduce that the inequality

1 \leq a_{1} \leq a_{2} \leq \ldots \leq a_{11} \leq 2015

is equivalent to the inequality

0 \leq k_{1} \leq k_{2} \leq k_{3} < k_{4} < k_{5} < k_{6} \leq k_{7} \leq k_{8} \leq k_{9} < k_{10} < k_{11} \leq 167

which is equivalent to

\begin{aligned} 0 \leq & k_{1} < k_{2} + 1 < k_{3} + 2 < k_{4} + 2 < k_{5} + 2 < k_{6} + 2 < \\ & < k_{7} + 3 < k_{8} + 4 < k_{9} + 5 < k_{10} + 5 < k_{11} + 5 \leq 172 . \end{aligned}

Therefore, there are

\binom{173}{11}

such sequences.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.