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 "2025 AIME I Problems/Problem 5"

(→‎Solution 1)
Line 4: Line 4:
  
 
==Solution 1==
 
==Solution 1==
−
Notice that if the 8-digit number is divisible by 22, it must have an even unit's digit. Therefore, we can break it up into cases and let the last digit be either 2, 4, 6, or 8. This problem is symmetric so we may assume that once we find the number of cases for one of these numbers, say 2, then we multiply by 4. Now, we just need to find how to positions of the rest of the numbers can there be such that the unit's digit is 2 and the number is divisible by 11. If we remember the divisibility rule for 11, then we can denote the odd numbered positions to be a1, a3, a5, and a7 and the even numbered positions to be a2, a4, and a6. Now, by the divisibility rule, we must have:
+
Notice that if the 8-digit number is divisible by <math>22</math>, it must have an even units digit. Therefore, we can break it up into cases and let the last digit be either <math>2, 4, 6,</math> or <math>8</math>. Due to symmetry, upon finding the total count of one of these last digit cases (we look at last digit <math>2</math> here), we may multiply the resulting value by <math>4</math>.
−
(a1 + a3 + a5 + a7) - (a2 + a4 + a6 + 2) which is congruent to 0(mod 11). Therefore, by simplifying, we must have:
+
 
−
a1 - a2 + a3 - a4 + a5 - a6 + a7 to be congruent to 2(mod 11). Now, let's consider a1 + a2 + ... + a7. This is just 1 + 2 + ... + 8 - 2 as we have already used up 2 as our unit's digit. This sum simplifies to 34 which is congruent to 1(mod 11). Therefore, we can say that (a1 + a2 + ... + a7) - 2(a2 + a4 + a6) is congruent to 2(mod 11) which means a2 + a4 + a6 is congruent to 5(mod 11). Notice the least sum this could even have is 1 + 3 + 4 = 8 and the greatest sum of a2 + a4 + a6 is 6 + 7 + 8 = 21. So the only possible number congruent to 5(mod 11) in this range is 16. So now, we just have to count up all the possible sums of 16 using the values 1, 3, 4, 5, 6, 7, and 8. We get: <math>(1, 7, 8), (3, 5, 8), (3, 6, 7)</math>, and <math>(4, 5, 7)</math> counting a total of 4 pairs. Notice now, the arrangement of the odd-positioned numbers doesn't matter so we can say it is 4! or 24 ways. The arrangement of each of these new 4 pairs we have just found is 3! = 6. Thus, for the unit's digit to be 2, we have 24*6*4 possible ways. Since we claimed that this was symmetric over the rest of the even digit unit's digits, we have to multiply this by 4 again. So our total number of ways is 24*6*4*4 = 2304. Thus, the positive difference between N and 2025 is 2304 - 2025 = <math>\boxed{279}</math>.
+
 
 +
Now, we just need to find the number of positions of the remaining numbers such that the units digit is <math>2</math> and the number is divisible by <math>11</math>. Denote the odd numbered positions to be <math>a_1, a_3, a_5, a_7</math> and the even numbered positions to be <math>a_2, a_4, a_6</math> (recall <math>a_8=2</math>). By the divisibility rule of <math>11</math>, we must have:
 +
<cmath>(a_1 + a_3 + a_5 + a_7) - (a_2 + a_4 + a_6 + 2)</cmath>
 +
which is congruent to <math>0\hspace{2mm}(\text{mod}\hspace{1mm}11)</math>. Therefore, after simplifying, we must have:
 +
<cmath>a_1 - a_2 + a_3 - a_4 + a_5 - a_6 + a_7\equiv2\hspace{2mm}(\text{mod}\hspace{1mm}11)</cmath>
 +
Now consider <math>a_1+ a_2 +\ldots + a_7=1+2+\ldots+8-2=34\equiv1\hspace{2mm}(\text{mod}\hspace{1mm}11)</math>. Therefore,
 +
<cmath>(a_1 + a_2 + \ldots+ a_7) - 2(a_2 + a_4 + a_6)\equiv2\hspace{2mm}(\text{mod}\hspace{1mm}11)</cmath>
 +
which means that
 +
<cmath>a_2 + a_4 + a_6\equiv5\hspace{2mm}(\text{mod}\hspace{1mm}11)</cmath>
 +
Notice that the minimum of <math>a_2+a_4+a_6</math> is <math>1 + 3 + 4 = 8</math> and the maximum is <math>6 + 7 + 8 = 21</math>. The only possible number congruent to <math>5\hspace{2mm}(\text{mod}\hspace{1mm}11)</math> in this range is <math>16</math>. All that remains is to count all the possible sums of <math>16</math> using the values <math>1, 3, 4, 5, 6, 7, 8</math>. There are a total of four possibilities:
 +
<cmath>(1, 7, 8), (3, 5, 8), (3, 6, 7), (4, 5, 7)</cmath>
 +
The arrangement of the odd-positioned numbers (<math>a_1,a_3,a_5,a_7</math>) does not matter, so there are <math>4!=24</math> arrangements of these numbers. Recall that the <math>4</math> triplets above occupy <math>a_2,a_4,a_6</math>; the number of arrangements is <math>3!=6</math>. Thus, we have <math>24\cdot6\cdot4=576</math> possible numbers such that the units digit is <math>2</math>. Since we claimed symmetry over the rest of the units digits, we must multiply by <math>4</math>, resulting in <math>576\cdot4=2304</math> eight-digit positive integers. Thus, the positive difference between <math>N</math> and <math>2025</math> is <math>2304 - 2025 = \boxed{279}</math>.
  
 
~ilikemath247365
 
~ilikemath247365
 +
 +
~LaTeX by eevee9406
  
 
==See also==
 
==See also==

Revision as of 21:47, 13 February 2025

Problem

There are $8!= 40320$ eight-digit positive integers that use each of the digits $1, 2, 3, 4, 5, 6, 7, 8$ exactly once. Let $N$ be the number of these integers that are divisible by $22$. Find the difference between $N$ and $2025$.

Solution 1

Notice that if the 8-digit number is divisible by $22$, it must have an even units digit. Therefore, we can break it up into cases and let the last digit be either $2, 4, 6,$ or $8$. Due to symmetry, upon finding the total count of one of these last digit cases (we look at last digit $2$ here), we may multiply the resulting value by $4$.


Now, we just need to find the number of positions of the remaining numbers such that the units digit is $2$ and the number is divisible by $11$. Denote the odd numbered positions to be $a_1, a_3, a_5, a_7$ and the even numbered positions to be $a_2, a_4, a_6$ (recall $a_8=2$). By the divisibility rule of $11$, we must have: \[(a_1 + a_3 + a_5 + a_7) - (a_2 + a_4 + a_6 + 2)\] which is congruent to $0\hspace{2mm}(\text{mod}\hspace{1mm}11)$. Therefore, after simplifying, we must have: \[a_1 - a_2 + a_3 - a_4 + a_5 - a_6 + a_7\equiv2\hspace{2mm}(\text{mod}\hspace{1mm}11)\] Now consider $a_1+ a_2 +\ldots + a_7=1+2+\ldots+8-2=34\equiv1\hspace{2mm}(\text{mod}\hspace{1mm}11)$. Therefore, \[(a_1 + a_2 + \ldots+ a_7) - 2(a_2 + a_4 + a_6)\equiv2\hspace{2mm}(\text{mod}\hspace{1mm}11)\] which means that \[a_2 + a_4 + a_6\equiv5\hspace{2mm}(\text{mod}\hspace{1mm}11)\] Notice that the minimum of $a_2+a_4+a_6$ is $1 + 3 + 4 = 8$ and the maximum is $6 + 7 + 8 = 21$. The only possible number congruent to $5\hspace{2mm}(\text{mod}\hspace{1mm}11)$ in this range is $16$. All that remains is to count all the possible sums of $16$ using the values $1, 3, 4, 5, 6, 7, 8$. There are a total of four possibilities: \[(1, 7, 8), (3, 5, 8), (3, 6, 7), (4, 5, 7)\] The arrangement of the odd-positioned numbers ($a_1,a_3,a_5,a_7$) does not matter, so there are $4!=24$ arrangements of these numbers. Recall that the $4$ triplets above occupy $a_2,a_4,a_6$; the number of arrangements is $3!=6$. Thus, we have $24\cdot6\cdot4=576$ possible numbers such that the units digit is $2$. Since we claimed symmetry over the rest of the units digits, we must multiply by $4$, resulting in $576\cdot4=2304$ eight-digit positive integers. Thus, the positive difference between $N$ and $2025$ is $2304 - 2025 = \boxed{279}$.

~ilikemath247365

~LaTeX by eevee9406

See also

2025 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_AIME_I_Problems/Problem_5&oldid=242378"