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 "2003 AIME II Problems/Problem 2"

 
(→‎Solution 2)
 
(15 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
Let <math>N</math> be the greatest integer multiple of 8, no two of whose digits are the same. What is the remainder when <math>N</math> is divided by 1000?
  
 
== Solution ==
 
== Solution ==
 +
We want a number with no digits repeating, so we can only use the digits <math>0-9</math> once in constructing our number. To make the greatest number, we want the greatest digit to occupy the leftmost side and the least digit to occupy the rightmost side. Therefore, the last three digits of the greatest number should be an arrangement of the digits <math>0,1,2</math>. Since the number has to be divisible by 8, the integer formed by the arrangement of <math>0,1,2</math> is also divisible by 8. The only arrangement that works is <math>120</math>.
 +
 +
Therefore, the remainder when the number is divided by <math>1000</math> is <math>\boxed{120}</math>.
 +
 +
Note: The number is <math>9876543120</math>
 +
 +
==Solution 2==
 +
We notice that the number doesn't matter after the thousands place because any place higher will be divisible by 8. Therefore, the number will look like this(with the maximizing constraint):
 +
 +
<math>9876543abc</math>
 +
 +
The abc is there because we don't have the guarantee of divisibility by 8. abc will be a rearrangement of <math>0, 1, 2</math>
 +
 +
Now all we have to do is look for the smallest rearrangement of 0, 1, 2.
 +
We can write a congruence statement as shown:
 +
 +
<math>100a+10b+10c \cong 0 \mod 8</math>
 +
 +
which simplifies to:
 +
 +
<math>4a+2b+c \cong 0 \mod 8</math>
 +
 +
Now, since we want to minimize the number, we can first try the case when a = 0.
 +
 +
This doesn't work, as 2+0 isn't congruent to 0 mod 8.
 +
 +
Now lets try a = 1.
 +
 +
We have <math>4 + 2b + c \cong 0 \mod 8</math>
 +
 +
From which we get 120 as the smallest.
 +
 +
Now, taking adding that to the number, we get 9876543120. Getting the remainder mod 1000 gives <math>\boxed{120}</math>
  
 
== See also ==
 
== See also ==
−
* [[2003 AIME II Problems]]
+
{{AIME box|year=2003|n=II|num-b=1|num-a=3}}
 +
 
 +
[[Category: Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 10:35, 18 August 2024

Problem

Let $N$ be the greatest integer multiple of 8, no two of whose digits are the same. What is the remainder when $N$ is divided by 1000?

Solution

We want a number with no digits repeating, so we can only use the digits $0-9$ once in constructing our number. To make the greatest number, we want the greatest digit to occupy the leftmost side and the least digit to occupy the rightmost side. Therefore, the last three digits of the greatest number should be an arrangement of the digits $0,1,2$. Since the number has to be divisible by 8, the integer formed by the arrangement of $0,1,2$ is also divisible by 8. The only arrangement that works is $120$.

Therefore, the remainder when the number is divided by $1000$ is $\boxed{120}$.

Note: The number is $9876543120$

Solution 2

We notice that the number doesn't matter after the thousands place because any place higher will be divisible by 8. Therefore, the number will look like this(with the maximizing constraint):

$9876543abc$

The abc is there because we don't have the guarantee of divisibility by 8. abc will be a rearrangement of $0, 1, 2$

Now all we have to do is look for the smallest rearrangement of 0, 1, 2. We can write a congruence statement as shown:

$100a+10b+10c \cong 0 \mod 8$

which simplifies to:

$4a+2b+c \cong 0 \mod 8$

Now, since we want to minimize the number, we can first try the case when a = 0.

This doesn't work, as 2+0 isn't congruent to 0 mod 8.

Now lets try a = 1.

We have $4 + 2b + c \cong 0 \mod 8$

From which we get 120 as the smallest.

Now, taking adding that to the number, we get 9876543120. Getting the remainder mod 1000 gives $\boxed{120}$

See also

2003 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
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=2003_AIME_II_Problems/Problem_2&oldid=225248"