Author |
Topic: Four-digit palindromes. (Read 1386 times) |
|
rloginunix
Uberpuzzler
Posts: 1029
|
 |
Four-digit palindromes.
« on: Jun 20th, 2014, 10:02am » |
 Quote  Modify
|
Four-digit palindromes.
Prove that all the four-digit palindromes are evenly divisible by eleven.
Definition.
A digital palindrome is a number that has the same value whether it's read left to right or right to left. For example: 5335, 98789, 123454321, etc.
|
|
 IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Four-digit palindromes.
« Reply #1 on: Jun 20th, 2014, 3:20pm » |
Quote Modify
|
Not necessarily super-rigorously worded, but it should be convincing enough:
0000 is arguably divisible by eleven, and if that doesn't count as a base case, then 0110 is divisible by eleven, and so is 1001, depending on what you consider to be a '4 digit number'.
Now, let a be a digit.
If a00a is divisible by eleven, then so is a11a. if a11a is, so is a22a, etc...
Whichever you start at just add 110 to show that the next one is divisible by eleven too.
If a99a is divisible by eleven, and b is the next digit after a, then then just add eleven to a99a to get
b00b, which is therefore also divisible by eleven.
So all of them are divisible by eleven, right up to 9999.
You could also use this result:
http://www.artofproblemsolving.com/Wiki/index.php/Divisibility_rules/Rul e_for_11_proof
|
| « Last Edit: Jun 20th, 2014, 3:23pm by dudiobugtron » |
IP Logged |
|
|
|
0.999...
Full Member
Gender: 
Posts: 156
|
|
Re: Four-digit palindromes.
« Reply #2 on: Jun 20th, 2014, 3:52pm » |
Quote Modify
|
| hidden: |
The numbers of the form 100..001 with an even number of zeros are all divisible by 11, since 102k-1+1=(-1)2k-1+1=0(mod 11). Thus, we can append any number of zeros to the end of such a number, like 100100, and still have it be divisible by 11. Call the numbers Nk,l where 2k zeros occur between the 1s and l zeros occur at the end.
A palindrome with an even number of digits takes the form
a1a2...anan..a1=Nn-1,0a1+Nn-2,1a2+...+N0,n-1a n
and therefore it is divisible by 11.
|
|
| « Last Edit: Jun 20th, 2014, 3:53pm by 0.999... » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Four-digit palindromes.
« Reply #3 on: Jun 21st, 2014, 10:15am » |
Quote Modify
|
Well done.
I'd qualify your proofs as "proof by construction" - examine how the given objects are constructed, find the pattern, make the conclusion.
dudiobugtron, a tiny remark about the case of switching from a99a to b00b. Of course jumping to the fact that you add eleven is correct but in the spirit of your deduction I would say you first add 1001 and then you subtract 990 to get 11.
0.999..., you proved even a more generic case.
I'll add my proof since it's a bit different. Based on the Division Algorithm Theorem, for integers a and b <> 0 there exist unique integers q and r such that a = q*b + r. Our task is to prove that Digital Palindrome of four digits DP(4) = 11*b with r == 0.
Let T be the thousands digit and H be the hundreds digit. Then DP(4) = THHT or in base 10 form DP(4) = 1000*T + 100*H + 10*H + T = 1001*T + 110*H = 11*91*T + 11*10*H = 11*(91*T + 10*H) = 11*b, where b == 91*T + 10*H.
P.S.
For this particular problem, to call an object a four-digit number, I'd say, means that the size-defining digit must be > 0. So the smallest four-digit palindrome is 1001, etc.
P.S.P.S
I took this problem from "Thinking Mathematically" by Mason J., Burton L., Stacey K.
|
|
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Four-digit palindromes.
« Reply #4 on: Jun 21st, 2014, 2:00pm » |
Quote Modify
|
That is an elegant proof, rloginunix 
I think for the easy forum, your astute observation that THHT = 1001*T + 110*H is probably enough, or at least the most important bit to point out.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Four-digit palindromes.
« Reply #5 on: Jun 21st, 2014, 2:35pm » |
Quote Modify
|
Guys, I was thinking (the credit here goes to 0.999... for the generic idea) - yet another way to prove the generic case is by induction.
1). Basis for the induction.
For a 2k-digit palindrome if k = 1 then we have a trivial case of aa = 10*T + T = 11*T where T denotes the Tens digit.
2). Induction hypothesis.
Any 2k-digit palindrome is evenly divisible by 11. Note here that any such palindrome can be represented in terms of "next"/"previous" as DP(2k) = a*10^(2k-1) +DP(2k-2)*10 + a. For example, 5335 is "next" and 33 is "previous": 5335 = 5*1000 + 33*10 + 5. The key here is that 33*10 ("previous") is always divisible by 11.
3). Induction step.
Let k = k + 1. Then DP(2k+2) = b*10^(2k+1) + DP(2k) + b = b*(10^(2k+1) + 1) + DP(2k). By hypothesis DP(2k) is evenly divisible by 11. What remains to be proven is that (10^(2k+1) + 1) is evenly divisible by 11.
But 0.999... gave such proof, one. Two, pex also proved that fact in Factorable if m is odd thread.
And I think we're done.
The only other generalization I see at the moment is to prove the above generic statement for any base, not necessarily ten.
[edit]
Fixed the "Induction hypothesis" typo: 3 became 5 as it should've been.
[/edit]
|
| « Last Edit: Jun 22nd, 2014, 10:37am by rloginunix » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Four-digit palindromes.
« Reply #6 on: Jun 21st, 2014, 8:57pm » |
Quote Modify
|
I convinced myself that it is true in a more intuitive or visual way.
A number consisting in a digit repeated an even number of times can be grouped in 2-digits parts making it obvious it is a multilpe of 11.
777777 is 77'77'77, assembled from 77's that are multiples of 11.
If you ignore the first and last digit, you still have an even number of digits and a multiple of 11. You can remove the center part.
In the example above, you can subtract the 7777 in the middle of 777777 to get 700007. It remains a multiple of 11.
This works for any digit replacing 7, and any even number of 0's.
You can then assemble such numbers by "inserting" one into the other to produce any palindrome you like, if it has an even number of digits.
The base is completely irrelevant.
|
| « Last Edit: Jun 21st, 2014, 8:59pm by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Four-digit palindromes.
« Reply #7 on: Jun 22nd, 2014, 7:10am » |
Quote Modify
|
on Jun 21st, 2014, 8:57pm, Grimbal wrote:| The base is completely irrelevant. |
|
As long as "eleven" (in the original problem statement) means 11 (b+1) in the same base (b) as the palindrome, rather than one more than the usual number of fingers people have.
|
| « Last Edit: Jun 22nd, 2014, 7:11am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Four-digit palindromes.
« Reply #8 on: Jun 22nd, 2014, 11:46am » |
Quote Modify
|
Yes, that's what I meant but failed to convey (sorry):
any palindrome that has 2k base B digits is evenly divisible by B + 1
For example, hex AA = decimal 170 is evenly divisible by 17 (16 + 1). Hex ABBA = decimal 43962 is evenly divisible by 17 - it's 2586.
It looks like a curious invariant. I mean if I were to ask (in vacuum) "what do 170 and 43962 have in common?" without switching to a different base the answer is not that obvious (I think). These decimal numbers lack the symmetry and have more than one common divisor.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Four-digit palindromes.
« Reply #9 on: Jun 22nd, 2014, 12:53pm » |
Quote Modify
|
In general if you add the odd-positioned digits and subtract the even-positioned digits, then the number is divisible by 11 iff the result of said calculation is.
(And so if the odd-positioned numbers equal the even-positioned ones in some permutation, as they do for an even-length palindrome, that's trivially the case).
[edit]Clarified odd/even vs odd/even-positioned issue pointed out by dudiobugtron below[/edit]
|
| « Last Edit: Jun 22nd, 2014, 10:15pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Four-digit palindromes.
« Reply #10 on: Jun 22nd, 2014, 1:24pm » |
Quote Modify
|
By 'odd digits', I assume you mean the first, 3rd, 5th, etc.. digits; not the ones which are themselves odd numbers.
on Jun 22nd, 2014, 11:46am, rloginunix wrote:| "what do 170 and 43962 have in common?" |
|
They're both divisible by 34. 
|
|
IP Logged |
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Four-digit palindromes.
« Reply #11 on: Jun 22nd, 2014, 7:30pm » |
Quote Modify
|
That is quite nice, Grimbal. I especially like that it indicates how to calculate 10...01/11.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Four-digit palindromes.
« Reply #12 on: Jun 22nd, 2014, 10:15pm » |
Quote Modify
|
on Jun 22nd, 2014, 1:24pm, dudiobugtron wrote:| By 'odd digits', I assume you mean the first, 3rd, 5th, etc.. digits; not the ones which are themselves odd numbers. |
|
Yes, that's what I meant.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Annettagiles
Junior Member
Gender:
Posts: 67
|
|
Re: Four-digit palindromes.
« Reply #13 on: Sep 25th, 2014, 4:12am » |
Quote Modify
|
3663 is the correct palindrome which will be get divisible by eleven easily.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Four-digit palindromes.
« Reply #14 on: Sep 26th, 2014, 4:55am » |
Quote Modify
|
on Jun 22nd, 2014, 12:53pm, towr wrote:In general if you add the odd-positioned digits and subtract the even-positioned digits, then the number is divisible by 11 iff the result of said calculation is.
(And so if the odd-positioned numbers equal the even-positioned ones in some permutation, as they do for an even-length palindrome, that's trivially the case). |
|
In fact, you can go further - if you number the positions from the right, so the units position will always be the first position, then the sum of the digits in odd positions less the sum of the digits in even positions will equal the original number mod 11.
The proof is pretty trivial:
10=-1 (mod 11)
so
SUMi=0n { 10iai } = SUMi=0n { (-1)iai }
= SUMi=0n/2 { a2i } - SUMi=0n/2 { a2i + 1 }
Which happens to be independent of the base used.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print