How many 4 digit palindromes are divisible by 7 ?
Details and assumptions
A palindrome is a number that is the same when its digits are reversed (i.e. 2 3 2 is a palindrome).
The number 1 0 = 0 1 0 is not considered a 3-digit palindrome. It only has 2 digits, and we ignore any 0's at the start.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Clear and brief solution, great! By the way, there is an AMC 10 problem that is nearly identical to this one.
Log in to reply
Log in to reply
The AMC's are the American Mathematics Competitions, probably the largest math contests taken in the United States. The AMC 10 and 12 are the first tests in a series of examinations used to determine the United States IMO team. The AIME is taken by the top scorers on the AMC 10 and AMC 12. A combination of AMC and AIME scores determines who takes the USA(J)MO, a proof-based , two-day test in similar format to the IMO. The top 12 scorers on the USAMO are invited to a summer camp in June, where they are rigorously trained. The top 6 from there are selected to go on to the IMO. There are more details that I left out, but those are the basics.
Log in to reply
@Tanishq Aggarwal – That explains it, thanks Tanishq!
Yeah, this one.
I accidentally got that wrong on Math Madness, oops. xD
Very elegant solution! Brilliant thinking, Pranav! :)
good
Consider 4 digit palindrome ABBA
ABBA can be rewritten as 1001A + 110B
Since 1001 is divisible by 7, we only need to have 110B divisible by 7 to satisfy the condition.
110 shares no factors with 7, so we need B to be divisible by 7 in order for 110B to be divisble by 7. Thus, B is either 0 or 7.
Since A can be any number from 1 to 9, we have 2* 9 = 18 possibilities.
A 4 digit palindrome can be unambiguously determined by its last two digits. Let the last two digits be b a . This means, the palindrome can be written as a b b a , a = 0 .
a b b a = 1 0 0 0 a + 1 0 0 b + 1 0 b + a = 1 0 0 1 a + 1 1 0 b = 7 ⋅ 1 4 3 a + 1 1 0 b
Therefore, for the palindrome to be divisible by 7 , b must divide 7 . This means b can either be 0 or 7 . For each value of b , a can take on 9 values ( 1 , 2 , … , 9 ). Therefore, there are 1 8 possibilities.
Let the number be A B B A , where A = 0 . This number is 1 0 0 0 A + 1 0 0 B + 1 0 B + A . For 7 to be a factor of this number, we have 7 ∣ ( 1 0 0 1 A + 1 0 1 B ) , but 7 ∣ 1 0 0 1 , so 1 0 0 1 A is always divisible by 7 . This gives us 7 ∣ ( 1 0 1 B ) ⟹ 7 ∣ B ⟹ B ∈ { 0 , 7 } . At this point, if B is 0 or 7 , it does not matter what A is. The palindrome will always be divisible by 7 in such cases.
There are 9 ways this can happen in the case where B = 0 and 9 ways this can happen in the case where B = 7 . Thus, the answer is 9 + 9 = 1 8 .
Correction: Every time I say 1 0 1 , I mean 1 1 0 . This does not affect the above solution since 7 ∤ 1 1 0 either. Sorry about that!
Suppose the palindrome is a b b a .
a b b a = 1 0 0 1 a + 1 1 0 b
Clearly 7 ∣ 1 0 0 1 a ,
so 7 ∣ 1 1 0 b
Since 7 ∤ 1 1 0
so 7 ∣ b
b = 0 o r 7
There are 9 possibilities for a, 2 for b
Total: 9 ∗ 2 = 1 8
abba = 1001a + 110b
since 1001 is divisible by 7 so a is range from any 1-9 --> 9 possibles
since 110 is not divisible by 7 and both are coprimed numbers so b is divisible by 7
b = 0 or 7 --> 2 possibles
so all possibles abba is 9x2 = 18
Note that a 4-digit palinrome can be written as n = 1 0 0 0 a + 1 0 0 b + 1 0 b + a , which is n = 1 0 0 1 a + 1 1 0 b Now, we want n ≡ 0 ( m o d 7 ) ; but n ≡ ≡ ≡ 1 0 0 1 a + 1 1 0 b 0 a + 5 b 5 b ( m o d 7 ) So we are looking for b s such that 5 b ≡ 0 ( m o d 7 ) , which actually is, multiplying by 3 , b ≡ 0 ( m o d 7 ) which leads to b ∈ { 0 , 7 } Notice that a can be chosen arbitrarily from 1 to 9 (remember that a palindrome cannot start with 0 . So we have 9 choices for a and 2 choices for b , for a total of 9 ⋅ 2 = 1 8 such n s
1 0 0 1 is divisible by 7 . So, we get 1 0 0 1 , 2 0 0 2 , … 9 0 0 9 is divisible by 7 .
Then the only palindromes we can make from that is if we add 7 7 0 in 1 0 0 1 and its multiples until 9 0 0 9 , so we get a total of 9 + 9 = 1 8 numbers.
First, we express the palindrome as 1 0 0 0 a + 1 0 0 b + 1 0 b + a . Using the well-known divisibility rule for 7 , we see that as a is the last digit, 1 0 0 0 a + 1 0 0 b + 1 0 b + a ≡ 1 0 0 a + 1 0 b + b − 2 a ≡ 9 8 a + 1 1 b ≡ 4 b ( m o d 7 ) , as 7 ∣ 9 8 . Thus, 4 b ≡ 0 ( m o d 7 ) ⟹ b = 0 , 7 . As each choice of b gives an equal number of palindromes, exactly 5 1 of the palindromes are divisible by 7 . Since there are 9 choices for a and 1 0 choices for b , exactly 5 1 ⋅ 9 ⋅ 1 0 = 1 8 of these palindromes are divisible by 7 .
For this solution I used this divisibility test:
Since the number is a palindrome the ones digit and the thousands digit are the same, x, so when you use the divisibility test you can sum the products of the ones digit and the thousands digit together like this (1 + 6)(x) = 7x.
We can also do this for the tens and hundreds digit, since they are also the same, as (3 + 2)y = 5y. So the sum will be 7x + 5y.
For this sum to be a multiple of 7, 7x must be 0 or a multiple of 7 and 5y must be 0 or a multiple of 7. Since x represents the thousands digit it cannot be a 0 because then it will be a 3 digit number and also since its coefficient is 7 no matter what digit x is it will be a multiple of 7, so there are 9 possibilities for x. y can be 0 and the only digit that makes a multiple of 7 is 7, giving 35, so there are 2 possibilities for y. Therefore the answer is 9 × 2 = 1 8
First we consider numbers ending and products ending when multiplied by 7.
1 x 7 = 7, 2 x 7 = 4, 3 x 7 = 1, 4 x 7 = 8, 5 x 7 = 5, 6 x 7 = 2, 7 x 7 = 9, 8 x 7 = 6, 9 x 7 = 3, 0 x 7 = 0,
So for a 4 digit palindrome we must have a pattern of ABBA or AAAA
means that the first and last number is the same and the second and third number is the same also.
According to the number ending and product ending. In ABBA or AAAA, A could be any number from 1-9 since we can't have a number that starts with zero.
For example,
If our A is 1 then our number would be 1BB1. Finding the possible values of B, we could get 0 and 7 ----> (1001, 1771)
so all in all, we could have 9 possible values of A and each value of A can take either 0 or 7 on their B's.
so 9 x 2 = 18
I see that 1001 is divisible by seven. And then if you add 770, keeping it a palindrome, it's still divisible by 7. So do it to 2002, (multiple of 1001) and so on until 9779. Which is 18.
1) palindromes will be of the form 'abab' or abba
2) now for a 4 digit number wxyz to be divisible by seven, (6w + 2x + 3y + z) should be divisible by seven
3) now consider the first palindrome 'abab'. for it to be divisible by seven (6a+2b+3a+b) must be divisible by 7, which implies [3(3a + b)] must be divisible by seven, which implies (3a+b) should be divisible by seven. now since a and b are digits they will be less than or equal to 9 and a cant be 0. there for 0<a<10 there are solutions to make (3a+b) divisible by 7.
therefore there are 9 numbers of the for 'abab' divisible by 7
4) similarly there are 9 numbers of the form 'abba' divisible by 7
5)there total 18 numbers are possible
remember 1001 is divisible by 7. So we get 1001, 2002, etc till 9009 is divisible by 7
Then the only palindromes we can make from that is if we add 770, so we get a total of 9+9 = 18 numbers. 1001, 1771, 2002, 2772, etc
All 4 digit palindromes can be written in the form "xyyx". We remind ourselves here that x lies between 0 and 9,and it CAN NOT be 0,while y also lies between 0 and 9,but CAN be 0. The number can be expressed as 1001x+110y=N. Now 7 | 1001 but not 110.So the number to be divisible by 7,7 should divide y,and hence y can be either 0 or 7. For each of the values of y,x have 9 values (running from 1 to 9).So total number of such N's is 9+9=18.
as 1 0 0 ≡ 1 , 1 0 1 ≡ 3 , 1 0 2 ≡ 2 , 1 0 3 ≡ 6 . . . ( m o d 7 )
so for any number a b b a , it is divisible by 7 if ( a ∗ 6 + b ∗ 2 + b ∗ 3 + a ∗ 1 ) is divisible by 7 ⇒ 7 a + 5 b is divisible by 7
so b must be divisible by 7 ⇒ b=0 ,or 7
b=0 in 9 numbers, a=1:9
b=7 in 9 numbers, a=1:9
so we have 18 numbers
I wrote all the palindromic 4-digit nos. then remembering the rule for divisibility test for 7, I started to test from 1001 which I found exactly divisible by 7 and the next is 1771 that I found also divisible by 7. then I found 2002 and 2772 also both divisible by 7. Noting the pattern, I predicted (and found true) that there will be two multiples of 7 among those palindromic nos. beginning with 3, two for nos. beginning with 4 and so on. From 1 to 9 then, of two each, equals 18.
Let N be a 4-digit palindrome number and a and b are digits. Then N must be in the form a b b a
Thus we can expand a b b a = 1 0 0 0 a + 1 0 0 b + 1 0 b + a
= 1 0 0 1 a + 1 1 0 b
= ( ( 1 4 3 × 7 ) a + ( 1 5 × 7 ) b + 5 b
= 7 × ( 1 4 3 a + 1 5 b ) + 5 b
Since 7 × ( 1 4 3 a + 1 5 b ) + 5 b is clearly divisible by 7, then to make N divisible by 7 the following condition must true :
5 b ≡ 0 ( m o d 7 )
So there are only 2 possibilities for b , those are 0 and 7 .
Since a has no effect on the divisibility of N by 7, and a cannot be 0 because the resulting number will be 3-digits, thus there are 9 possibility of a [ 1 . . 9 ] .
So, by rule of product, the answer is 9 × 2 = 1 8
We write the palidrome numbers as n = 1 0 0 0 a + 1 0 0 b + 1 0 b + a = 1 0 0 1 a + 1 1 0 b with a , b ∈ ( 1 , 2 , 3 , . . . , 8 , 9 ) . With modulus 7 we get:
1 0 0 1 a + 1 1 0 b ≡ 0 × a + 5 b ≡ 5 b m o d 7
We see that 7 has to be a multiple of 7. So b = 7 o r b = 0 and a ∈ ( 1 , 2 , 3 , . . . , 8 , 9 ) so the total number of palindromes which 7 divides is 9 × 2 = 1 8 .
We know that for any number that is divisible by 7, when the twice the last digit of the number is subtracted from the rest of the number, the resulting number is always a multiple of 7. For example, we know that the number 343 is divisible by 7. This is confirmed when we take its last digit, 3, double it (ie. 3 × 2 = 6 ), and subtract it from the rest of the number, which is 34, since the 3 is removed (ie. 3 4 − 6 = 2 8 ). Since 2 8 = 4 × 7 , we can therefore confirm that 343 is indeed a multiple of 7.
So, in the context of this question, we want to find 4-digit palindromes (of the form a b b a , where a and b are the digits of the palindrome) which are divisible by 7.
Thus, following from the divisibility rule of 7 in the first paragraph, for a 4-digit palindrome, a b b a , to be divisible by 7, the following must be true:
a b b − 2 a = 7 k , where k is an integer.
Since a b b is a number in base 10, we can change the equation to:
1 0 0 a + 1 0 b + b − 2 a = 7 k
9 8 a + 1 1 b = 7 k
7 ( 1 4 a + 7 1 1 b ) = 7 k
1 4 a + 7 1 1 b = k
We see that for k to be an integer, the term 7 1 1 b has to be an integer, which is only the case when b = 0 or b = 7 . On the other hand, the term 1 4 a is always an integer, so a = 1 , 2 , … , 9 , excluding a = 0 because it would cause a b b a to just be a 3-digit number.
Thus, since there are 9 possible numbers for a and 2 possible numbers for b , the number of 4 digit palindromes divisible by 7 is 9 × 2 = 1 8 .
Assume the palindrome occurs in the form abba. One must note that 1001 is divisible by 7, so if b=0, any value of a would make the number divisible by 7 since a00a would be divisible by 1001. Note that b=7 is another possibility as if a00a is divisible by 7, then a77a (a00a+770) is also divisible by 7 since 7 divides 770. Since all values of a except 0 are possible for each of the two cases, there are a total of 9 x 2=18 palindromes.
4-digit palindromes are of the form a b b a , where a and b are digits. Taking this number modulo 7, we have 1 0 0 0 a + 1 0 0 b + 1 0 b + a ≡ 0 ( m o d 7 ) 1 0 0 1 a + 1 1 0 b ≡ 0 ( m o d 7 ) 1 0 0 1 a + 1 1 0 b ≡ 0 ( m o d 7 ) 5 b ≡ 0 ( m o d 7 ) b ≡ 0 ( m o d 7 )
The only such b are 0 , 7 , and a can be any non-zero digit, so there are 2 × 9 = 1 8 such palindromes.
A four-digit number a b c d * is equal to 1 0 0 0 a + 1 0 0 b + 1 0 c + d in expanded form. (Make sure you see why.) However, if we want this number to be a palindrome, we need to have a = d and b = c . This leads us to
a b c d = 1 0 0 0 a + 1 0 0 b + 1 0 b + a
⟹ 1 0 0 1 a + 1 1 0 b
So a four digit palindrome is in the form 1 0 0 1 a + 1 1 0 b .
Now, we want this palindrome to be divisible by 7. Since 1 0 0 1 = 7 ⋅ 9 1 , we know that 1 0 0 1 a is divisible by 7, so 1 1 0 b must be divisible by 7 as well, in order for the whole thing to be divisible by 7. (We can show this by modular arithmetic.)
Since 110 is not divisible by 7, b must be divisible by 7, so either b = 0 or b = 7 .
There are 9 possible values of a , since we can't use 0 as a leading digit, and two values of b , so by multiplying, we have 9 ⋅ 2 = 1 8 4 digit palindromes divisible by 7.
* a b c d just means that a b c d is being treated as a number, not multiplied together like a ⋅ b ⋅ c ⋅ d
Edit: I previously said that 1 0 0 1 = 7 ⋅ 9 1 , but that should be read as 1 0 0 1 = 7 ⋅ 1 4 3 .
Let the 4-d number be ABBA .
Using the Divisibility Rule (see http://en.wikipedia.org/wiki/Divisibility_rule) , a number is divisible by 7 if the alternating sum of blocks of three from right to left is divisible by 7. E.g. 1,369,851: 851 − 369 + 1 = 483 = 7 × 69
Applying this, ABBA is divisible by 7 if BBA - A = BB0 (a three digit number with zero at the digits place) is divisible by 7, and thus, BB can only be 00 or 77 . (remember that BB are the same integers)
Applying this, any integer A, when paired with -00- or -77- will be divisible by 7. A can be 1-9, thus, ABBA = 1001, 2002, ..., 9009, ..., 1771, 2772, ..., 9779, = 18 PALINDROMES
Used a C program to determine the 4-digit palindromes and these are the following: 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992 3003, 3113, 3223, 3333, 3443, 3553, 3663, 3773, 3883, 3993 4004, 4114, 4224, 4334, 4444, 4554, 4664, 4774, 4884, 4994 5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995 6006, 6116, 6226, 6336, 6446, 6556, 6666, 6776, 6886, 6996 7007, 7117, 7227, 7337, 7447, 7557, 7667, 7777, 7887, 7997 8008, 8118, 8228, 8338, 8448, 8558, 8668, 8778, 8888, 8998 9009, 9119, 9229, 9339, 9449, 9559, 9669, 9779, 9889, 9999 Individually divides them by 7 to add the thrill in counting. :)
Any 4 digit palindrome can be rewritten as α 1 0 0 1 + β 1 1 0 for α = 1 , … , 9 , β = 0 , … 9 , notice that 1 0 0 1 ≡ 0 m o d 7 , so any α can satisfy the formula. This then just becomes equivalent to the problem of finding β such that β 1 1 0 ≡ 5 β ≡ 0 m o d 7 it's easy to verify that only β = 0 , 7 satisfies this equivalence, and so our solutions can be characterized by the pairwise sum { ( 1 , … , 9 ) 1 0 0 1 , { 0 , 7 } 1 1 0 } of which there are exactly 2 × 9 = 1 8 solutions.
Problem Loading...
Note Loading...
Set Loading...
Consider a 4 digit palindrome x y y x where x = 0 .
We can write x y y x as 1 0 0 0 x + 1 0 0 y + 1 0 y + x = 1 0 0 1 x + 1 1 0 y = 1 0 0 1 x + 1 0 5 y + 5 y .
Notice that 1 0 0 1 x is always divisible by 7 for any value of x . Similarly 1 0 5 y is also always divisible by 7 . For the number to be divisible by 7 , 5 y must be also divisible by 7 and for that we have only two possibilities i.e 0 and 7 .
So, we have 9 possibilities for x and 2 possibilities for y . So total number of palindromes are 9 × 2 = 1 8 .