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 "2001 AIME I Problems/Problem 1"

m (→‎Solution)
(→‎Solution 4)
(15 intermediate revisions by 6 users not shown)
Line 2: Line 2:
 
Find the sum of all positive two-digit integers that are divisible by each of their digits.
 
Find the sum of all positive two-digit integers that are divisible by each of their digits.
  
−
== Solution ==
+
== Solution 1 ==
−
We cannot have a 0 in the number if we want a real number.
+
Let our number be <math>10a + b</math>, <math>a,b \neq 0</math>. Then we have two conditions: <math>10a + b \equiv 10a \equiv 0 \pmod{b}</math> and <math>10a + b \equiv b \pmod{a}</math>, or <math>a</math> divides into <math>b</math> and <math>b</math> divides into <math>10a</math>. Thus <math>b = a, 2a,</math> or <math>5a</math> (note that if <math>b = 10a</math>, then <math>b</math> would not be a digit).
  
−
We split this up into cases:
+
*For <math>b = a</math>, we have <math>n = 11a</math> for nine possibilities, giving us a sum of <math>11 \cdot \frac {9(10)}{2} = 495</math>. 
 +
*For <math>b = 2a</math>, we have <math>n = 12a</math> for four possibilities (the higher ones give <math>b > 9</math>), giving us a sum of <math>12 \cdot \frac {4(5)}{2} = 120</math>.
 +
*For <math>b = 5a</math>, we have <math>n = 15a</math> for one possibility (again, higher ones give <math>b > 9</math>), giving us a sum of <math>15</math>.
 +
If we ignore the case <math>b = 0</math> as we have been doing so far, then the sum is <math>495 + 120 + 15 = \boxed{630}</math>.
  
−
Case 1: 11-19
+
== Solution 2 ==
−
Then the units digit must be a factor of the number, so 11, 12, and 15 work.
 
  
−
Case 2: 21-29
+
Using casework, we can list out all of these numbers: <cmath>11+12+15+22+24+33+36+44+48+55+66+77+88+99=\boxed{630}.</cmath>
  
−
The number must be even, so 22 and 24 work.
+
== Solution 3 ==
  
−
Case 3: 31-39
+
To further expand on solution 2, it would be tedious to test all <math>90</math> two-digit numbers. We can reduce the amount to look at by focusing on the tens digit.
 +
First, we cannot have any number that is a multiple of <math>10</math>. We also note that any number with the same digits is a number that satisfies this problem. This gives <cmath>11, 22, 33, ... 99.</cmath> We start from each of these numbers and constantly add the digit of the tens number of the respective number until we get a different tens digit. For example, we look at numbers <math>11, 12, 13, ... 19</math> and numbers <math>22, 24, 26, 28</math>. This heavily reduces the numbers we need to check, as we can deduce that any number with a tens digit of <math>5</math> or greater that does not have two of the same digits is not a valid number for this problem. This will give us the numbers from solution 2.
  
−
The number must be a multiple of 3, so only 33 and 36 work.
+
== Solution 4 ==
  
−
Case 4: 41-49
+
In this solution, we will do casework on the ones digit.
 +
Before we start, let's make some variables. Let <math>a</math> be the ones digit, and <math>b</math> be the tens digit. Let <math>n</math> equal our number. Our number can be expressed as <math>10b+a</math>. We can easily see that <math>b|a</math>, since <math>b|n</math>, and <math>b|10b</math>. Therefore, <math>b|(n-10b)</math>.
 +
Now, let's start with the casework.
  
−
It must be a multiple of 4, so 44 and 48  work.
+
Case 1: <math>a=1</math>
 +
Since <math>b|a</math>, <math>b=1</math>. From this, we get that <math>n=11</math> satisfies the condition.
  
−
Case 5: 51-59
+
Case 2: <math>a=2</math>
 +
We either have <math>b=1</math>, or <math>b=2</math>. From this, we get that <math>n=12</math> and <math>n=22</math> satisfy the condition.
  
−
It must be a multiple of 5, so only 55 works.
+
Case 3: <math>a=3</math>
 +
We have <math>b=3</math>. From this, we get that <math>n=33</math> satisfies the condition. Note that <math>b=1</math> was not included because <math>3</math> does not divide <math>13</math>.
  
−
Case 6: 61-69
+
Case 4: <math>a=4</math>
 +
We either have <math>b=2</math> or <math>b=4</math>. From this, we get that <math>n=24</math> and <math>n=44</math> satisfy the condition. <math>b=1</math> was not included for similar reasons as last time.
  
−
It must be a multiple of 6, so only 66 works.
+
Case 5: <math>a=5</math>
 +
We either have <math>b=1</math> or <math>b=5</math>. From this, we get that <math>n=15</math> and <math>n=55</math> satisfy the condition.
  
−
Case 7: 71-79
+
Continuing with this process up to <math>a=9</math>, we get that <math>n</math> could be <math>11, 12, 22, 33, 24, 44, 15, 55, 36, 66, 77, 48, 88, 99</math>. Summing, we get that the answer is <math>\boxed{630}</math>. A clever way to sum would be to group the multiples of <math>11</math> together to get <math>11+22+\dots+99=(45)(11)=495</math>, and then add the remaining <math>12+24+15+36+48=135</math>.
  
−
It must be a multiple of 7, so 77 is the only one that works.
+
<i>-bronzetruck2016<i>
−
 
 
−
Case 8: 81-89
 
−
 
 
−
It must be a multiple of 8, so only 88 works.
 
−
 
 
−
Case 9: 91-99
 
−
 
 
−
It must be a multiple  of 9, so only 99 works.
 
−
 
 
−
<math>11+12+15+22+24+33+36+44+48+55+66+77+88+99=\boxed{630}</math>
 
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2001|n=I|before=First Question|num-a=2}}
 
{{AIME box|year=2001|n=I|before=First Question|num-a=2}}
 +
 +
[[Category:Introductory Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 17:14, 16 April 2021

Problem

Find the sum of all positive two-digit integers that are divisible by each of their digits.

Solution 1

Let our number be $10a + b$, $a,b \neq 0$. Then we have two conditions: $10a + b \equiv 10a \equiv 0 \pmod{b}$ and $10a + b \equiv b \pmod{a}$, or $a$ divides into $b$ and $b$ divides into $10a$. Thus $b = a, 2a,$ or $5a$ (note that if $b = 10a$, then $b$ would not be a digit).

  • For $b = a$, we have $n = 11a$ for nine possibilities, giving us a sum of $11 \cdot \frac {9(10)}{2} = 495$.
  • For $b = 2a$, we have $n = 12a$ for four possibilities (the higher ones give $b > 9$), giving us a sum of $12 \cdot \frac {4(5)}{2} = 120$.
  • For $b = 5a$, we have $n = 15a$ for one possibility (again, higher ones give $b > 9$), giving us a sum of $15$.

If we ignore the case $b = 0$ as we have been doing so far, then the sum is $495 + 120 + 15 = \boxed{630}$.

Solution 2

Using casework, we can list out all of these numbers: \[11+12+15+22+24+33+36+44+48+55+66+77+88+99=\boxed{630}.\]

Solution 3

To further expand on solution 2, it would be tedious to test all $90$ two-digit numbers. We can reduce the amount to look at by focusing on the tens digit. First, we cannot have any number that is a multiple of $10$. We also note that any number with the same digits is a number that satisfies this problem. This gives \[11, 22, 33, ... 99.\] We start from each of these numbers and constantly add the digit of the tens number of the respective number until we get a different tens digit. For example, we look at numbers $11, 12, 13, ... 19$ and numbers $22, 24, 26, 28$. This heavily reduces the numbers we need to check, as we can deduce that any number with a tens digit of $5$ or greater that does not have two of the same digits is not a valid number for this problem. This will give us the numbers from solution 2.

Solution 4

In this solution, we will do casework on the ones digit. Before we start, let's make some variables. Let $a$ be the ones digit, and $b$ be the tens digit. Let $n$ equal our number. Our number can be expressed as $10b+a$. We can easily see that $b|a$, since $b|n$, and $b|10b$. Therefore, $b|(n-10b)$. Now, let's start with the casework.

Case 1: $a=1$ Since $b|a$, $b=1$. From this, we get that $n=11$ satisfies the condition.

Case 2: $a=2$ We either have $b=1$, or $b=2$. From this, we get that $n=12$ and $n=22$ satisfy the condition.

Case 3: $a=3$ We have $b=3$. From this, we get that $n=33$ satisfies the condition. Note that $b=1$ was not included because $3$ does not divide $13$.

Case 4: $a=4$ We either have $b=2$ or $b=4$. From this, we get that $n=24$ and $n=44$ satisfy the condition. $b=1$ was not included for similar reasons as last time.

Case 5: $a=5$ We either have $b=1$ or $b=5$. From this, we get that $n=15$ and $n=55$ satisfy the condition.

Continuing with this process up to $a=9$, we get that $n$ could be $11, 12, 22, 33, 24, 44, 15, 55, 36, 66, 77, 48, 88, 99$. Summing, we get that the answer is $\boxed{630}$. A clever way to sum would be to group the multiples of $11$ together to get $11+22+\dots+99=(45)(11)=495$, and then add the remaining $12+24+15+36+48=135$.

-bronzetruck2016

See also

2001 AIME I (Problems • Answer Key • Resources)
Preceded by
First Question 		Followed by
Problem 2
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=2001_AIME_I_Problems/Problem_1&oldid=151722"