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"

(Blanked the page)
(Tag: Blanking)
m (→‎Solution 3)
 
(39 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 +
==Problem==
  
 +
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==
 +
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>.
 +
 +
 +
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==
 +
{{AIME box|year=2025|num-b=4|num-a=6|n=I}}
 +
 +
{{MAA Notice}}

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"