2023 AIME I Problems/Problem 7

Unofficial problem statement: Find the number of positive integers from 1 to 1000 that have different mods in mod 2,3,4,5, and 6.

Unofficial Solution: We realize that any such number (mod 2) and (mod 4) must have the same parity, and its values (mod 3) and (mod 6) must have a absolute value difference of 3. Thus the only possibilities for the sequence of mods are 1,2,3,4,5 1,2,3,0,5 and 0,1,2,3,4. Using CRT and summing we get 049.

Solution

$\textbf{Case 0:} {\rm Rem} \ \left( n, 6 \right) = 0$ .

We have ${\rm Rem} \ \left( n, 2 \right) = 0$ . This violates the condition that $n$ is extra-distinct. Therefore, this case has no solution.

$\textbf{Case 1:} {\rm Rem} \ \left( n, 6 \right) = 1$ .

We have ${\rm Rem} \ \left( n, 2 \right) = 1$ . This violates the condition that $n$ is extra-distinct. Therefore, this case has no solution.

\textbf{Case 2:} {\rm Rem} \ \left( n, 6 \right) = 2$.

We have$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \ \left( n, 3 \right) = 2 $. This violates the condition that$ n $is extra-distinct. Therefore, this case has no solution.$ \textbf{Case 3:} {\rm Rem} \ \left( n, 6 \right) = 3$.

The condition$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \ \left( n, 6 \right) = 3 $implies$ {\rm Rem} \ \left( n, 2 \right) = 1 $,$ {\rm Rem} \ \left( n, 3 \right) = 0$.

Because$ (Error compiling LaTeX. Unknown error_msg)n $is extra-distinct,$ {\rm Rem} \ \left( n, l \right) $for$ l \in \left\{ 2, 3, 4 \right\} $is a permutation of$ \left\{ 0, 1 ,2 \right\} $. Thus,$ {\rm Rem} \ \left( n, 4 \right) = 2$.

However,$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \ \left( n, 4 \right) = 2 $conflicts$ {\rm Rem} \ \left( n, 2 \right) = 1 $. Therefore, this case has no solution.$ \textbf{Case 4:} {\rm Rem} \ \left( n, 6 \right) = 4$.

The condition$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \ \left( n, 6 \right) = 4 $implies$ {\rm Rem} \ \left( n, 2 \right) = 0 $and$ {\rm Rem} \ \left( n, 3 \right) = 1$.

Because$ (Error compiling LaTeX. Unknown error_msg)n $is extra-distinct,$ {\rm Rem} \ \left( n, l \right) $for$ l \in \left\{ 2, 3, 4 , 5 \right\} $is a permutation of$ \left\{ 0, 1 ,2 , 3 \right\}$.

Because$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \ \left( n, 2 \right) = 0 $, we must have$ {\rm Rem} \ \left( n, 4 \right) = 2 $. Hence,$ {\rm Rem} \ \left( n, 5 \right) = 3$.

Hence,$ (Error compiling LaTeX. Unknown error_msg)n \equiv -2 \pmod{{\rm lcm} \left( 4, 5 , 6 \right)} $. Hence,$ n \equiv - 2 \pmod{60}$.

We have$ (Error compiling LaTeX. Unknown error_msg)1000 = 60 \cdot 16 + 40 $. Therefore, the number extra-distinct$ n $in this case is 16.$ \textbf{Case 5:} {\rm Rem} \ \left( n, 6 \right) = 5$.

The condition$ (Error compiling LaTeX. Unknown error_msg){\rm Rem} \ \left( n, 6 \right) = 5 $implies$ {\rm Rem} \ \left( n, 2 \right) = 1 $and$ {\rm Rem} \ \left( n, 3 \right) = 2$.

Because$ (Error compiling LaTeX. Unknown error_msg)n $is extra-distinct,$ {\rm Rem} \ \left( n, 4 \right) $and$ {\rm Rem} \ \left( n, 5 \right) $are two distinct numbers in$ \left\{ 0, 3, 4 \right\} $. Because$ {\rm Rem} \ \left( n, 4 \right) \leq 3 $and$ n $is odd, we have$ {\rm Rem} \ \left( n, 4 \right) = 3 $. Hence,$ {\rm Rem} \ \left( n, 5 \right) = 0 $or 4.$ \textbf{Case 5.1:} {\rm Rem} \ \left( n, 6 \right) = 5 $,$ {\rm Rem} \ \left( n, 4 \right) = 3 $,$ {\rm Rem} \ \left( n, 5 \right) = 0$.

We have$ (Error compiling LaTeX. Unknown error_msg)n \equiv 35 \pmod{60}$.

We have$ (Error compiling LaTeX. Unknown error_msg)1000 = 60 \cdot 16 + 40 $. Therefore, the number extra-distinct$ n $in this subcase is 17.$ \textbf{Case 5.2:} {\rm Rem} \ \left( n, 6 \right) = 5 $,$ {\rm Rem} \ \left( n, 4 \right) = 3 $,$ {\rm Rem} \ \left( n, 5 \right) = 4 $.$ n \equiv - 1 \pmod{60}$.

We have$ (Error compiling LaTeX. Unknown error_msg)1000 = 60 \cdot 16 + 40 $. Therefore, the number extra-distinct$ n$in this subcase is 16.

Putting all cases together, the total number of extra-distinct$ (Error compiling LaTeX. Unknown error_msg)n $is$ 16 + 17 + 16 = \boxed{\textbf{(049) }}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Page

Toolbox

Search

2023 AIME I Problems/Problem 7

Solution