Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AIME I Problems/Problem 7"

m (→‎Solution)
m (→‎Solution)
Line 5: Line 5:
 
==Solution==
 
==Solution==
  
−
<math>\textbf{Case 0:} {\rm Rem} \ \left( n, 6 \right) = 0</math>.
+
<math>\textbf{Case 0: } {\rm Rem} \ \left( n, 6 \right) = 0</math>.
  
 
We have <math>{\rm Rem} \ \left( n, 2 \right) = 0</math>. This violates the condition that <math>n</math> is extra-distinct.
 
We have <math>{\rm Rem} \ \left( n, 2 \right) = 0</math>. This violates the condition that <math>n</math> is extra-distinct.
 
Therefore, this case has no solution.
 
Therefore, this case has no solution.
  
−
<math>\textbf{Case 1:} {\rm Rem} \ \left( n, 6 \right) = 1</math>.
+
<math>\textbf{Case 1: } {\rm Rem} \ \left( n, 6 \right) = 1</math>.
  
 
We have <math>{\rm Rem} \ \left( n, 2 \right) = 1</math>. This violates the condition that <math>n</math> is extra-distinct.
 
We have <math>{\rm Rem} \ \left( n, 2 \right) = 1</math>. This violates the condition that <math>n</math> is extra-distinct.
 
Therefore, this case has no solution.
 
Therefore, this case has no solution.
  
−
#\textbf{Case 2:} {\rm Rem} \ \left( n, 6 \right) = 2<math>.
+
<math>\textbf{Case 2: } {\rm Rem} \ \left( n, 6 \right) = 2</math>.
  
−
We have </math>{\rm Rem} \ \left( n, 3 \right) = 2<math>. This violates the condition that </math>n<math> is extra-distinct.
+
We have <math>{\rm Rem} \ \left( n, 3 \right) = 2</math>. This violates the condition that <math>n</math> is extra-distinct.
 
Therefore, this case has no solution.
 
Therefore, this case has no solution.
  
−
</math>\textbf{Case 3:} {\rm Rem} \ \left( n, 6 \right) = 3<math>.
+
<math>\textbf{Case 3: } {\rm Rem} \ \left( n, 6 \right) = 3</math>.
  
−
The condition </math>{\rm Rem} \ \left( n, 6 \right) = 3<math> implies </math>{\rm Rem} \ \left( n, 2 \right) = 1<math>, </math>{\rm Rem} \ \left( n, 3 \right) = 0<math>.
+
The condition <math>{\rm Rem} \ \left( n, 6 \right) = 3</math> implies <math>{\rm Rem} \ \left( n, 2 \right) = 1</math>, <math>{\rm Rem} \ \left( n, 3 \right) = 0</math>.
  
−
Because </math>n<math> is extra-distinct, </math>{\rm Rem} \ \left( n, l \right)<math> for </math>l \in \left\{ 2, 3, 4 \right\}<math> is a permutation of </math>\left\{ 0, 1 ,2 \right\}<math>.
+
Because <math>n</math> is extra-distinct, <math>{\rm Rem} \ \left( n, l \right)</math> for <math>l \in \left\{ 2, 3, 4 \right\}</math> is a permutation of <math>\left\{ 0, 1 ,2 \right\}</math>.
−
Thus, </math>{\rm Rem} \ \left( n, 4 \right) = 2<math>.
+
Thus, <math>{\rm Rem} \ \left( n, 4 \right) = 2</math>.
  
−
However, </math>{\rm Rem} \ \left( n, 4 \right) = 2<math> conflicts </math>{\rm Rem} \ \left( n, 2 \right) = 1<math>.
+
However, <math>{\rm Rem} \ \left( n, 4 \right) = 2</math> conflicts <math>{\rm Rem} \ \left( n, 2 \right) = 1</math>.
 
Therefore, this case has no solution.
 
Therefore, this case has no solution.
  
−
</math>\textbf{Case 4:} {\rm Rem} \ \left( n, 6 \right) = 4<math>.
+
<math>\textbf{Case 4: } {\rm Rem} \ \left( n, 6 \right) = 4</math>.
  
−
The condition </math>{\rm Rem} \ \left( n, 6 \right) = 4<math> implies </math>{\rm Rem} \ \left( n, 2 \right) = 0<math> and </math>{\rm Rem} \ \left( n, 3 \right) = 1<math>.
+
The condition <math>{\rm Rem} \ \left( n, 6 \right) = 4</math> implies <math>{\rm Rem} \ \left( n, 2 \right) = 0</math> and <math>{\rm Rem} \ \left( n, 3 \right) = 1</math>.
  
−
Because </math>n<math> is extra-distinct, </math>{\rm Rem} \ \left( n, l \right)<math> for </math>l \in \left\{ 2, 3, 4 , 5 \right\}<math> is a permutation of </math>\left\{ 0, 1 ,2 , 3 \right\}<math>.
+
Because <math>n</math> is extra-distinct, <math>{\rm Rem} \ \left( n, l \right)</math> for <math>l \in \left\{ 2, 3, 4 , 5 \right\}</math> is a permutation of <math>\left\{ 0, 1 ,2 , 3 \right\}</math>.
  
−
Because </math>{\rm Rem} \ \left( n, 2 \right) = 0<math>, we must have </math>{\rm Rem} \ \left( n, 4 \right) = 2<math>. Hence, </math>{\rm Rem} \ \left( n, 5 \right) = 3<math>.
+
Because <math>{\rm Rem} \ \left( n, 2 \right) = 0</math>, we must have <math>{\rm Rem} \ \left( n, 4 \right) = 2</math>. Hence, <math>{\rm Rem} \ \left( n, 5 \right) = 3</math>.
  
−
Hence, </math>n \equiv -2 \pmod{{\rm lcm} \left( 4, 5 , 6 \right)}<math>.
+
Hence, <math>n \equiv -2 \pmod{{\rm lcm} \left( 4, 5 , 6 \right)}</math>.
−
Hence, </math>n \equiv - 2 \pmod{60}<math>.
+
Hence, <math>n \equiv - 2 \pmod{60}</math>.
  
−
We have </math>1000 = 60 \cdot 16 + 40<math>.
+
We have <math>1000 = 60 \cdot 16 + 40</math>.
−
Therefore, the number extra-distinct </math>n<math> in this case is 16.
+
Therefore, the number extra-distinct <math>n</math> in this case is 16.
  
−
</math>\textbf{Case 5:} {\rm Rem} \ \left( n, 6 \right) = 5<math>.
+
<math>\textbf{Case 5: } {\rm Rem} \ \left( n, 6 \right) = 5</math>.
  
−
The condition </math>{\rm Rem} \ \left( n, 6 \right) = 5<math> implies </math>{\rm Rem} \ \left( n, 2 \right) = 1<math> and </math>{\rm Rem} \ \left( n, 3 \right) = 2<math>.
+
The condition <math>{\rm Rem} \ \left( n, 6 \right) = 5</math> implies <math>{\rm Rem} \ \left( n, 2 \right) = 1</math> and <math>{\rm Rem} \ \left( n, 3 \right) = 2</math>.
  
−
Because </math>n<math> is extra-distinct, </math>{\rm Rem} \ \left( n, 4 \right)<math> and </math>{\rm Rem} \ \left( n, 5 \right)<math> are two distinct numbers in </math>\left\{ 0, 3, 4 \right\}<math>.
+
Because <math>n</math> is extra-distinct, <math>{\rm Rem} \ \left( n, 4 \right)</math> and <math>{\rm Rem} \ \left( n, 5 \right)</math> are two distinct numbers in <math>\left\{ 0, 3, 4 \right\}</math>.
−
Because </math>{\rm Rem} \ \left( n, 4 \right) \leq 3<math> and </math>n<math> is odd, we have </math>{\rm Rem} \ \left( n, 4 \right) = 3<math>.
+
Because <math>{\rm Rem} \ \left( n, 4 \right) \leq 3</math> and <math>n</math> is odd, we have <math>{\rm Rem} \ \left( n, 4 \right) = 3</math>.
−
Hence, </math>{\rm Rem} \ \left( n, 5 \right) = 0<math> or 4.
+
Hence, <math>{\rm Rem} \ \left( n, 5 \right) = 0</math> or 4.
  
−
</math>\textbf{Case 5.1:} {\rm Rem} \ \left( n, 6 \right) = 5<math>, </math>{\rm Rem} \ \left( n, 4 \right) = 3<math>, </math>{\rm Rem} \ \left( n, 5 \right) = 0<math>.
+
<math>\textbf{Case 5.1: } {\rm Rem} \ \left( n, 6 \right) = 5</math>, <math>{\rm Rem} \ \left( n, 4 \right) = 3</math>, <math>{\rm Rem} \ \left( n, 5 \right) = 0</math>.
  
−
We have </math>n \equiv 35 \pmod{60}<math>.
+
We have <math>n \equiv 35 \pmod{60}</math>.
  
−
We have </math>1000 = 60 \cdot 16 + 40<math>.
+
We have <math>1000 = 60 \cdot 16 + 40</math>.
−
Therefore, the number extra-distinct </math>n<math> in this subcase is 17.
+
Therefore, the number extra-distinct <math>n</math> in this subcase is 17.
  
−
</math>\textbf{Case 5.2:} {\rm Rem} \ \left( n, 6 \right) = 5<math>, </math>{\rm Rem} \ \left( n, 4 \right) = 3<math>, </math>{\rm Rem} \ \left( n, 5 \right) = 4<math>.
+
<math>\textbf{Case 5.2: } {\rm Rem} \ \left( n, 6 \right) = 5</math>, <math>{\rm Rem} \ \left( n, 4 \right) = 3</math>, <math>{\rm Rem} \ \left( n, 5 \right) = 4</math>.
  
−
</math>n \equiv - 1 \pmod{60}<math>.
+
<math>n \equiv - 1 \pmod{60}</math>.
  
−
We have </math>1000 = 60 \cdot 16 + 40<math>.
+
We have <math>1000 = 60 \cdot 16 + 40</math>.
−
Therefore, the number extra-distinct </math>n<math> in this subcase is 16.
+
Therefore, the number extra-distinct <math>n</math> in this subcase is 16.
  
−
Putting all cases together, the total number of extra-distinct </math>n<math> is </math>16 + 17 + 16 = \boxed{\textbf{(049) }}$.
+
Putting all cases together, the total number of extra-distinct <math>n</math> is <math>16 + 17 + 16 = \boxed{\textbf{(049) }}</math>.
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Revision as of 16:08, 8 February 2023

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)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AIME_I_Problems/Problem_7&oldid=189061"