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 ${\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 ${\rm Rem} \ \left( n, 6 \right) = 3$ implies ${\rm Rem} \ \left( n, 2 \right) = 1$ , ${\rm Rem} \ \left( n, 3 \right) = 0$ .

Because $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, ${\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 ${\rm Rem} \ \left( n, 6 \right) = 4$ implies ${\rm Rem} \ \left( n, 2 \right) = 0$ and ${\rm Rem} \ \left( n, 3 \right) = 1$ .

Because $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 ${\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, $n \equiv -2 \pmod{{\rm lcm} \left( 4, 5 , 6 \right)}$ . Hence, $n \equiv - 2 \pmod{60}$ .

We have $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 ${\rm Rem} \ \left( n, 6 \right) = 5$ implies ${\rm Rem} \ \left( n, 2 \right) = 1$ and ${\rm Rem} \ \left( n, 3 \right) = 2$ .

Because $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 $n \equiv 35 \pmod{60}$ .

We have $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 $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 $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