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"

(→‎Problem)
m (→‎Solution 3)
 
(36 intermediate revisions by 7 users not shown)
Line 2: Line 2:
  
 
There are <math>8!= 40320</math> eight-digit positive integers that use each of the digits <math>1, 2, 3, 4, 5, 6, 7, 8</math> exactly once. Let <math>N</math> be the number of these integers that are divisible by <math>22</math>. Find the difference between <math>N</math> and <math>2025</math>.
 
There are <math>8!= 40320</math> eight-digit positive integers that use each of the digits <math>1, 2, 3, 4, 5, 6, 7, 8</math> exactly once. Let <math>N</math> be the number of these integers that are divisible by <math>22</math>. Find the difference between <math>N</math> and <math>2025</math>.
 +
 +
==Video solution by [[User:grogg007|grogg007]]==
 +
https://youtu.be/PNBxBvvjbcU?t=636
  
 
==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), and (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
 +
 
 +
~LaTeX by eevee9406
 +
 
 +
==Solution 2==
 +
1. To be multiple of <math>11:</math>
 +
Total of <math>1,2,3,4,5,6,7,8</math> is <math>36,</math> dividing into two groups of <math>4</math> numbers, the difference of sum of two group <math>x</math> and <math>y</math> need to be <math>0</math> or multiple of <math>11,</math> i.e. <math>x+y=36,</math> <math>x-y=0,11,22\dots</math> only <math>x=y=18</math> is possible.
 +
Number <math>8</math> can only be with <math>(8,1,4,5),(8,1,2,7),(8,1,3,6),(8,2,3,5).</math>
 +
One group of <math>4</math> numbers make <math>4!</math> different arrangement, two groups make <math>4!\cdot{4!},</math> the <math>2</math> group makes <math>2!</math> arrangement. The two group of numbers are alternating by digits.
 +
Total number of multiple of <math>11</math> is <math>4\cdot 2!\cdot 4!\cdot 4!.</math>
 +
2. To be multiple of <math>2:</math>
 +
We noticed in each number group, there are two odd two even.
 +
So the final answer is above divided by <math>2,</math> <math>4*2!*4!*4!/2=2304.</math>
 +
<math>2304-2025=\boxed{279.}</math>
 +
 
 +
~Mathzu.club
 +
~Latex by mathkiddus
 +
 
 +
==Solution 3==
 +
<cmath>
 +
\begin{array}{|c|c|c|c|c|c|c|c|}
 +
\hline
 +
w & a & x & b & y & c & z & n \\
 +
\hline
 +
\end{array}
 +
</cmath>
 +
Let <math>waxbyczn</math> be our 8 digit number. For a number to be a multiple of <math>22</math> it must be an even multiple of <math>11,</math> so <math>n</math> must be even and <math>|(w + x + y + z) - (a + b + c + n)| = 11x</math> for <math>1 \geq x \geq 0.</math> Let <math>n = 8.</math> We have three main subcases:
 +
 
 +
* SC1: <math>x = 0,</math> <math>a + b + c + 8 = w + x + y + z</math>
 +
 
 +
Note that none of the variables can be <math>8</math> since <math>n</math> is <math>8</math>. We know that <math>(a + b + c) + (w + x + y + z) = 28</math> and <math>(a + b + c) + 8 = (w + x + y + z).</math> Solving this system, we find <math>a + b + c = 10</math> and <math>w + x + y + z = 18.</math> After some small bashing we find there are <math>4</math> combinations of numbers that will work:
 +
the variables <math>a, b, c</math> can be distinct elements of the sets <math>\{2, 3, 5\}, \{1, 4, 5\}, \{1, 3, 6\}</math> or <math>\{1, 2, 7\}</math>, and <math>w, x, y, z</math> can be distinct elements of each corresponding set. (So for example, if we chose <math>a, b, c</math> from <math>\{2, 3, 5\}</math> we would choose <math>w, x, y, z</math> from <math>\{1, 4, 6, 7\},</math> the "corresponding" set). There are <math>4</math> different set pairs, <math>3!</math> ways to permute <math>a, b, c,</math> and <math>4!</math> ways to permute <math>w, x, y, z,</math> giving us <math>4! \cdot 3! \cdot 4</math> ways for this subcase.
 +
 
 +
* SC2: <math>x = 1,</math> <math>a + b + c + 19 = w + x + y + z</math>
 +
 
 +
<math>19</math> is odd, but <math>a + b + c + w + x + y + z</math> is even, so if we set up our system of equations for <math>(a + b + c)</math> and <math>(w + x + y + z)</math> like we did in sub case 1, we would end up with a fraction for the sums.
 +
 
 +
* SC3: <math>x = 1,</math> <math>a + b + c - 3  = w + x + y + z</math>
 +
Same issue as sub case 2, we will end up with a fraction because <math>3</math> is odd.
 +
 
 +
For every even <math>n</math>, there will always be <math>4! \cdot 3! \cdot 4</math> ways for SC1 (pretty easy to confirm this, just do SC1 for <math>n = 6,4,2</math>) and <math>0</math> ways for SC2 and SC3 since they will always give fractions for the sums when we try to set up our system. Since <math>n</math> can be <math>4</math> different values, the answer is <math>4! \cdot 3! \cdot 4 \cdot 4 - 2025 = \boxed{279}.</math>
 +
 
 +
~[[User:grogg007|grogg007]]
 +
 
 +
==Video Solution by SpreadTheMathLove==
 +
https://www.youtube.com/watch?v=P6siafb6rsI
 +
 
 +
(also the person in the Youtube video wrote the final answer wrong, it was supposed to be 279 and he accidentally wrote it as 729)
 +
 
 +
~Mathycoder
  
 
==See also==
 
==See also==

Latest revision as of 03:01, 24 July 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$.

Video solution by grogg007

https://youtu.be/PNBxBvvjbcU?t=636

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

Solution 2

1. To be multiple of $11:$ Total of $1,2,3,4,5,6,7,8$ is $36,$ dividing into two groups of $4$ numbers, the difference of sum of two group $x$ and $y$ need to be $0$ or multiple of $11,$ i.e. $x+y=36,$ $x-y=0,11,22\dots$ only $x=y=18$ is possible. Number $8$ can only be with $(8,1,4,5),(8,1,2,7),(8,1,3,6),(8,2,3,5).$ One group of $4$ numbers make $4!$ different arrangement, two groups make $4!\cdot{4!},$ the $2$ group makes $2!$ arrangement. The two group of numbers are alternating by digits. Total number of multiple of $11$ is $4\cdot 2!\cdot 4!\cdot 4!.$ 2. To be multiple of $2:$ We noticed in each number group, there are two odd two even. So the final answer is above divided by $2,$ $4*2!*4!*4!/2=2304.$ $2304-2025=\boxed{279.}$

~Mathzu.club ~Latex by mathkiddus

Solution 3

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline w & a & x & b & y & c & z & n \\ \hline \end{array}\] Let $waxbyczn$ be our 8 digit number. For a number to be a multiple of $22$ it must be an even multiple of $11,$ so $n$ must be even and $|(w + x + y + z) - (a + b + c + n)| = 11x$ for $1 \geq x \geq 0.$ Let $n = 8.$ We have three main subcases:

  • SC1: $x = 0,$ $a + b + c + 8 = w + x + y + z$

Note that none of the variables can be $8$ since $n$ is $8$. We know that $(a + b + c) + (w + x + y + z) = 28$ and $(a + b + c) + 8 = (w + x + y + z).$ Solving this system, we find $a + b + c = 10$ and $w + x + y + z = 18.$ After some small bashing we find there are $4$ combinations of numbers that will work: the variables $a, b, c$ can be distinct elements of the sets $\{2, 3, 5\}, \{1, 4, 5\}, \{1, 3, 6\}$ or $\{1, 2, 7\}$, and $w, x, y, z$ can be distinct elements of each corresponding set. (So for example, if we chose $a, b, c$ from $\{2, 3, 5\}$ we would choose $w, x, y, z$ from $\{1, 4, 6, 7\},$ the "corresponding" set). There are $4$ different set pairs, $3!$ ways to permute $a, b, c,$ and $4!$ ways to permute $w, x, y, z,$ giving us $4! \cdot 3! \cdot 4$ ways for this subcase.

  • SC2: $x = 1,$ $a + b + c + 19 = w + x + y + z$

$19$ is odd, but $a + b + c + w + x + y + z$ is even, so if we set up our system of equations for $(a + b + c)$ and $(w + x + y + z)$ like we did in sub case 1, we would end up with a fraction for the sums.

  • SC3: $x = 1,$ $a + b + c - 3 = w + x + y + z$

Same issue as sub case 2, we will end up with a fraction because $3$ is odd.

For every even $n$, there will always be $4! \cdot 3! \cdot 4$ ways for SC1 (pretty easy to confirm this, just do SC1 for $n = 6,4,2$) and $0$ ways for SC2 and SC3 since they will always give fractions for the sums when we try to set up our system. Since $n$ can be $4$ different values, the answer is $4! \cdot 3! \cdot 4 \cdot 4 - 2025 = \boxed{279}.$

~grogg007

Video Solution by SpreadTheMathLove

https://www.youtube.com/watch?v=P6siafb6rsI

(also the person in the Youtube video wrote the final answer wrong, it was supposed to be 279 and he accidentally wrote it as 729)

~Mathycoder

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

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