- New Logic/Math Puzzles - BrainDen.com

November 17, 2010

So you managed to solve the first part of this problem That problem proved to be easy enough. Now, to move to the second part:

Repeat the "Reverse - subtract - Reverse - add" steps from the first problem (see spoiler below), but this time starting with a 4 digit number. For example:

Starting with n= 1234

Reverse(n) = 4321

4321 - 1234 = 3087

Reverse(3087) = 7803

3087 + 7803 = 10890

The problem is as before. Do these steps performed on a four digit number always result in the number 10890? If so, prove it. If not, find an exception.

If the first question was easy, then I would say this one is about medium difficulty, because one can't enumerate the results on the first subtraction as easily. If you manage to solve this one, I've got a "hard" problem coming up after this...

1. Start with any 3 digit number, that isn't the same when written backwards (e.g. 123 is allowed, but 121 is not).
2. Write it backwards, and subtract the smaller from the larger (e.g. 321 - 123 = 198).
3. Take this number, reverse it again, but this time, add the reversed number (e.g. 198 + 891 = 1089).

Does this final answer always equal 1089? If so, prove it. If not, find an exception.

If you run into any 1 or 2 digit numbers along the way, treat them as having a leading zero. (e.g. think of "99" as "099", which, when reversed, would be written as 990. Similarly 100, when reversed, would be 001, or simply 1.)

Edit: As before, you can assume the initial 4 digit number not a palindrome (i.e. is different when reversed). Bonus question: if the initial number is not palindromic, can the result after the first subtraction be palindromic? If not, why not? If yes, under what conditions?

Edited November 17, 2010 by rajat_magic

araver · November 17, 2010

Do these steps performed on a four digit number always result in the number 10890? If so, prove it. If not, find an exception.

Edit: As before, you can assume the initial 4 digit number not a palindrome (i.e. is different when reversed).

No, it does not always result in 10890. The result of this sequence of operations is 0 for palidromic numbers and 990, 9999, 10989 and 10890 for the rest of the numbers.

Proof:
Let N=abcd=1000*a+100*b+10*c+d, where N is not palindromic.
Reverse(N)=dcba=1000*d+100*c+10*b+a.
Let F(N) = abs(N-Reverse(N))
Note that F(N)=F(Reverse(N)) so without loss of generality we can assume that N>Reverse(N).
F(N)= 1000*a+100*b+10*c+d-(1000*d+100*c+10*b+a)=999*(a-d)+90*(b-c).
Since N is not palindromic abs(a-d)+abs(b-c)>0.
It is easy to see that 0<F(N)<9999. Let F(N)=xyzt.

Case 1) If a=d then abs(b-c)>0. Since we assummed that N>Reverse(N) we get b>c.
Then F(N)=90*(b-c). Therefore F(N) is a multiple of 90: {090, 180, 270, 360, 450, 540, 630, 720, 810}.

Case 2) If a>d.
xyzt=F(N)=999*(a-d)+90*(b-c). We shall prove that x+t=10 and y+z=8.

First, note that 999*(a-d) can only yield {999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}.
We have two subcases:
Case 2.1) b<=c, implies 90*(b-c)<0.
90*(b-c) is in {0, -90, -180, -270, -360, -450, -540, -630, -720, -810}
Since -810<= 90*(b-c) the first digit of F(N), namely x, is not affected by 90*(b-c) and is determined only by the first digit of 999*(a-d). More precisely x = a-d-1.

Case 2.2) b>c, implies 90*(b-c) is in {090, 180, 270, 360, 450, 540, 630, 720, 810}
Since 9<90*(b-c)<1000 the first digit of F(N), namely x is equal to the first digit of 999*(a-d) plus 1 from the addition of the last 3 digits of 999*(a-d) and 90*(b-c).
In this case x = (a-d-1)+1.

Also, since 90*(b-c) is a multiple of 90: {090, 180, 270, 360, 450, 540, 630, 720, 810}, the least important digit t is not affected by 90*(b-c) and comes exclusively from 999*(a-d)={999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}.
More precisely t = 10-(a-d) (in both cases 2.1 and 2.2)

Then we have:
Case 2.1) x+t = 10-(a-d)+a-d-1=9.

Case 2.2) x+t = 10-(a-d)+(a-d-1)+1=10.
Now let's see y+z in the two cases. Case 2.1) b<=c, implies 90*(b-c)<0. 90*(b-c) is in {0, -90, -180, -270, -360, -450, -540, -630, -720, -810}. 999*(a-d) is in {999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}. It is easy to see that the middle digits of F(N), namely y and z are determined by substracting 9*(b-c) from 99. So 10*y+z is in {99,90,81,72,63,54,45,36,27,18}. We get y+z=9 if b<c and y+z=18 if b=c.
Case 2.1.1) b<c, y+z=9

Case 2.1.2) b=c, y+z=18
Case 2.2) b>c, implies 90*(b-c) is in {090, 180, 270, 360, 450, 540, 630, 720, 810} 999*(a-d) is in {999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}. It is easy to see that the middle digits of F(N), namely y and z, are determined by adding 9*(b-c) to 99 and ignoring the transport that is carried on (this transport is actually the one discussed when computing x in the case 2.1 above). So 10*y+z is in {8,17,26,35,44,53,62,71,80}.
Case 2.2) y+z=8.
Let M = xyzt. R(M) = M + Reverse(M) = 1000*x+100*y+10*z+t+1000*t+100*z+10*y+x = 1001*(x+t)+110*(y+z).
Case 1)     (a=d)		For x+t=0 and y+z=9 we have R(M)=110*9 = 990.

Case 2.1.1) (a>d, b<c) 		For x+t=9 and y+z=9 we have R(M)=1001*9+110*9 = 9999

Case 2.1.2) (a>d, b=c)		For x+t=9 and y+z=18 we have R(M)=1001*9+110*18 = 10989

Case 2.2)   (a>d, b>c)		For x+t=10 and y+z=8 we have R(M)=1001*10+110*8 = 10890.
Note that we assumed that N>Reverse(N) to simplify the proof, so the cases are reffering to abcd as max(N,Reverse(N)).

Bonus question: if the initial number is not palindromic, can the result after the first subtraction be palindromic? If not, why not? If yes, under what conditions?

Yes, it can be palidromic.
Assume F(N) is palindromic. Then x=t and y=z. Therefore x+t and y+z must be even. This eliminates all but case 2.2 above.
In case 2.2, if F(N) is palindromic then x=t=5 and y=z=4.
Since t = 10-(a-d) in case 2.2, we get a-d=5.
Since the middle digits of F(N), namely y and z, are determined by adding 9*(b-c) to 99 and ignoring the transport that is carried on we get 44 only if 9*(b-c)=45. So b-c=5.

So, a=d+5 and b=c+5. So F(N) is palindromic for all N with a=d+5 and b=c+5 and all reverses of these N.
E.g. N=5500 - F(N)=5445.

November 17, 2010

No, it does not always result in 10890. The result of this sequence of operations is 0 for palidromic numbers and 990, 9999, 10989 and 10890 for the rest of the numbers.

Proof:
Let N=abcd=1000*a+100*b+10*c+d, where N is not palindromic.
Reverse(N)=dcba=1000*d+100*c+10*b+a.
Let F(N) = abs(N-Reverse(N))
Note that F(N)=F(Reverse(N)) so without loss of generality we can assume that N>Reverse(N).
F(N)= 1000*a+100*b+10*c+d-(1000*d+100*c+10*b+a)=999*(a-d)+90*(b-c).
Since N is not palindromic abs(a-d)+abs(b-c)>0.
It is easy to see that 0<F(N)<9999. Let F(N)=xyzt.

Case 1) If a=d then abs(b-c)>0. Since we assummed that N>Reverse(N) we get b>c.
Then F(N)=90*(b-c). Therefore F(N) is a multiple of 90: {090, 180, 270, 360, 450, 540, 630, 720, 810}.

Case 2) If a>d.
xyzt=F(N)=999*(a-d)+90*(b-c). We shall prove that x+t=10 and y+z=8.

First, note that 999*(a-d) can only yield {999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}.
We have two subcases:
Case 2.1) b<=c, implies 90*(b-c)<0.
90*(b-c) is in {0, -90, -180, -270, -360, -450, -540, -630, -720, -810}
Since -810<= 90*(b-c) the first digit of F(N), namely x, is not affected by 90*(b-c) and is determined only by the first digit of 999*(a-d). More precisely x = a-d-1.

Case 2.2) b>c, implies 90*(b-c) is in {090, 180, 270, 360, 450, 540, 630, 720, 810}
Since 9<90*(b-c)<1000 the first digit of F(N), namely x is equal to the first digit of 999*(a-d) plus 1 from the addition of the last 3 digits of 999*(a-d) and 90*(b-c).
In this case x = (a-d-1)+1.

Also, since 90*(b-c) is a multiple of 90: {090, 180, 270, 360, 450, 540, 630, 720, 810}, the least important digit t is not affected by 90*(b-c) and comes exclusively from 999*(a-d)={999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}.
More precisely t = 10-(a-d) (in both cases 2.1 and 2.2)

Then we have:
Case 2.1) x+t = 10-(a-d)+a-d-1=9.

Case 2.2) x+t = 10-(a-d)+(a-d-1)+1=10.
Now let's see y+z in the two cases. Case 2.1) b<=c, implies 90*(b-c)<0. 90*(b-c) is in {0, -90, -180, -270, -360, -450, -540, -630, -720, -810}. 999*(a-d) is in {999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}. It is easy to see that the middle digits of F(N), namely y and z are determined by substracting 9*(b-c) from 99. So 10*y+z is in {99,90,81,72,63,54,45,36,27,18}. We get y+z=9 if b<c and y+z=18 if b=c.
Case 2.1.1) b<c, y+z=9

Case 2.1.2) b=c, y+z=18
Case 2.2) b>c, implies 90*(b-c) is in {090, 180, 270, 360, 450, 540, 630, 720, 810} 999*(a-d) is in {999, 1998, 2997, 3996, 4995, 5994, 6993, 7992, 8991}. It is easy to see that the middle digits of F(N), namely y and z, are determined by adding 9*(b-c) to 99 and ignoring the transport that is carried on (this transport is actually the one discussed when computing x in the case 2.1 above). So 10*y+z is in {8,17,26,35,44,53,62,71,80}.
Case 2.2) y+z=8.
Let M = xyzt. R(M) = M + Reverse(M) = 1000*x+100*y+10*z+t+1000*t+100*z+10*y+x = 1001*(x+t)+110*(y+z).
Case 1)     (a=d)		For x+t=0 and y+z=9 we have R(M)=110*9 = 990.

Case 2.1.1) (a>d, b<c) 		For x+t=9 and y+z=9 we have R(M)=1001*9+110*9 = 9999

Case 2.1.2) (a>d, b=c)		For x+t=9 and y+z=18 we have R(M)=1001*9+110*18 = 10989

Case 2.2)   (a>d, b>c)		For x+t=10 and y+z=8 we have R(M)=1001*10+110*8 = 10890.
Note that we assumed that N>Reverse(N) to simplify the proof, so the cases are reffering to abcd as max(N,Reverse(N)).
Yes, it can be palidromic.
Assume F(N) is palindromic. Then x=t and y=z. Therefore x+t and y+z must be even. This eliminates all but case 2.2 above.
In case 2.2, if F(N) is palindromic then x=t=5 and y=z=4.
Since t = 10-(a-d) in case 2.2, we get a-d=5.
Since the middle digits of F(N), namely y and z, are determined by adding 9*(b-c) to 99 and ignoring the transport that is carried on we get 44 only if 9*(b-c)=45. So b-c=5.

So, a=d+5 and b=c+5. So F(N) is palindromic for all N with a=d+5 and b=c+5 and all reverses of these N.
E.g. N=5500 - F(N)=5445.

Thats a great analysis, i came up with the same thing. I came up with a different solution for one of the cases in your proof though. The only difference i had was:

When a=d,990 is not necessarily correct.
take the number 1231. reversing and subtracting it gives 1321-1231 = 90. reversing and adding gives 99 because there is no longer a hundreds place or a thousands place in 90. i dont think you can count the existance of those place holders in the number because otherwise you could look at the reverse of 1231 as 13210 or 132100 ect.. If you reverse the numbers without using the lost thousands digit, you get the following:

dcba-abcd = 100(c-b)+10(c-b)+0 = 100(c-b-1)+10(10-c+b) + 0
this number is less than 1000, so there is no longer a thousands digit when reversing it; thus adding the reverse of the number gives
100(c-b-1) + 100(0) + 10(10-c+b)*2 + 0 + c-b-1
= 100c-100b-10c+10b+c+b-1+100
=81c-81b+99

If i made a mistake somewhere or my analysis is wrong let me know. Thanks!

November 17, 2010

I just randomly picked a number and here is what I got. Am I missing something?

I picked randomly 6719

6719
9176
9176 - 6719 = 2457
7542
7542 + 2457 = 9999

araver · November 18, 2010

Thats a great analysis, i came up with the same thing. I came up with a different solution for one of the cases in your proof though. The only difference i had was:

When a=d,990 is not necessarily correct.
take the number 1231. reversing and subtracting it gives 1321-1231 = 90. reversing and adding gives 99 because there is no longer a hundreds place or a thousands place in 90. i dont think you can count the existance of those place holders in the number because otherwise you could look at the reverse of 1231 as 13210 or 132100 ect.. If you reverse the numbers without using the lost thousands digit, you get the following:

dcba-abcd = 100(c-b)+10(c-b)+0 = 100(c-b-1)+10(10-c+b) + 0
this number is less than 1000, so there is no longer a thousands digit when reversing it; thus adding the reverse of the number gives
100(c-b-1) + 100(0) + 10(10-c+b)*2 + 0 + c-b-1
= 100c-100b-10c+10b+c+b-1+100
=81c-81b+99

If i made a mistake somewhere or my analysis is wrong let me know. Thanks!

Actually, I think the OP suggests that the Reverse function always works on 4 digits.

In the first problem, on 3 digits, it was explicitly stated how to treat numbers with less than 3 digits:

If you run into any 1 or 2 digit numbers along the way, treat them as having a leading zero. (e.g. think of "99" as "099", which, when reversed, would be written as 990. Similarly 100, when reversed, would be 001, or simply 1.)

Since this problem says that it works as the first problem, that it is an extension of the first problem, I think the natural assumption is to use the same type of function for reverse i.e. put leading zeros before reverse.

Formally,

Reverse_4 (N) = (N/1000%10)+(N/100%10)*10+(N/10%10)*100+(N%10)*1000.

where / is integer division ignoring remainders (aka DIV) and % is modulo operation (aka MOD). For arbitrary n, n-digit reverse can be written as:

Reverse_n (N)= Sum_(i=0)^(n-1) [N / 10^(n-i-1) % 10 * 10^i]

or in a more human-readable way:


               n-1        n-i-1          i

Reverse_n (N)= Sum [N / 10      % 10 * 10  ]

               i=0

November 18, 2010

Once again, great job araver.

Incidentally, take three of the four possible answers you have found: (990, 9999, 10989), and divide by 11. This gives (90, 909, 999), which are three of the possible four "stable states" of problem. Just an interesting observation.

November 18, 2010

ahh great catch araver, i must have missed that in the first problem. Thanks :-)

Sign In

Question

Guest

Link to comment

Share on other sites

6 answers to this question

Recommended Posts

araver

Link to comment

Share on other sites

Guest

Link to comment

Share on other sites

Guest

Link to comment

Share on other sites

araver

Link to comment

Share on other sites

Guest

Link to comment

Share on other sites

Guest

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members

Browse

Activity