[Guest]

Define R(n) as the function that "reverses the digits" of the number n, when written as a four digit number (with leading zeros if necessary). For example: R(1234) = 4321, R(5200)= 0025 = 25, and similarly R(25)=R(0025)=5200.

Define F(n) as function returning the absolute value of n - R(n). For example: F(1234) = |1234 - 4321| = 3087

Problem:

Show that, starting with any natural number below 9999, if the function F(n) is performed repeatedly, one (and only one) of the following numbers eventually shows up: 0, 90, 909, 999, 6534.

Example:

F(1234) = 3087

F(3087) = 4716

F(4716) = 1458

F(1458) = 7083

F(7083) = 3276

F(3276) = 3447

F(3447) = 3996

F(3996) = 2997

F(2997) = 4995

F(4995) = 999

Clearly, this is very simple to show with a computer, but I was looking for a more interesting solution.

[araver]

Clearly, this is very simple to show with a computer, but I was looking for a more interesting solution.

An analytical proof is possible, considering a smaller number of cases (instead of computing all F(.) sequences for all N's).

Yet I'm not sure if it is what you were looking for.

Let F(N)=xyzt. Let P(N) obtained by repeateadly applying F() until a cycle is reached i.e. stop when F(P(N)) is equal to a previously obtained number. Indeed, P(N) is either 0,6534,999,90,909.

It can be proved analitically, by splitting into cases. Normally I would consider discussing a small number of cases as an acceptable proof if the number of cases are much smaller than the actual number of possibilities for N (10000 in this case since 0 <= N <= 9999).

Let x-t=alpha, y-z=beta.

Considering that

 -9 <= alpha, beta <= 9

there are about 19*19=361 pairs (alpha, beta) possible. Well, 361 is better than 10000 by a factor of 27, so it might qualify as a very long analytical proof IMHO. Fortunately some cases are easier to discuss altogether (e.g. if alpha=beta or alpha=0 or beta=0). The fact that F(N) xyzt is not random, but the result of F() helps narrowing it down, (especially when alpha and beta are both odd) since there are only four main cases for x+t, y+z - discussed

Case 1)     (a=d)		x+t=0 and y+z=9 

Case 2.1.1) (a>d, b<c) 		x+t=9 and y+z=9 

Case 2.1.2) (a>d, b=c)		x+t=9 and y+z=18 

Case 2.2)   (a>d, b>c)		x+t=10 and y+z=8 

I found out that of the possible values, 0 and 6534 can be easily determined (only appear in case 1 below), the others are a little harder to determine.

Case 1) x-t=alpha=beta=y-z. 

If alpha is 0, 5 or -5 then P(N)=0

else P(N)=6534

More precisely: If alpha is 0 then N=xyyx, F(N)=0 or F(N)=5445 in which case F(F(N))=0; If alpha is 5 then F(N)=7722; F(F(N))=5445; F(F(F(N)))=0; If alpha is -5 then F(N)=2277; F(F(N))=5445; F(F(F(N)))=0; For the other values, alpha determines after how many F's you stop. E.g for alpha = 2, F(N) = 6534. for alpha =6 or -6, F(F(N)) = 6534. The cycles that get you to 6534 in at most 5 steps are:

8811 -> 7623 -> 4356 -> 2178 -> 6534

5544 -> 1089 -> 8712 -> 6534

Case 2) y-z=beta=0 and alpha <> 0 

Then P(N)=999.

Again, alpha determines after how many F's you stop. E.g. alpha=-9 then F(N)=999 The cycles that get you to 999 in at most 6 steps are: 6 steps:

  4446 (or 6444) -> 1998 -> 6993 -> 2997 -> 4995 -> 999

5 steps:

  1998 (or 8991) -> 6993 -> 2997 -> 4995 -> 999

  3447 (or 7443) -> 6993 -> 2997 -> 4995 -> 999

4 steps:

  1449 (or 1449) -> 7992 -> 4995 -> 999

  3996 (or 6993) ->	2997 -> 4995 -> 999

3 steps:

  2448 (or 8442) -> 5994 -> 999

  2997 (or 7992) -> 4995 -> 999

2 steps:

  4995 (or 5994) -> 999

Case 3) x-y=alpha=0 and beta <> 0 

Then P(N)=90.

Case 4) alpha <>0 and beta <>0 and alpha <> beta.

Then P(N) is either 90 or 999 or 909.

But I found no way I can prove it unless taking each possible (alpha, beta) pair and discussing each case. Some pairs can get you to very long computations. E.g. (alpha, beta)=(6,-8) gives a 14-long cycle:

8082 -> 5274 -> 549 -> 8901 -> 7803 -> 4716 -> 1458 -> 7083 -> 3276 -> 3447 -> 3996 ->	2997 ->	4995 -> 999

Another 14-long cycle is obtained for (alpha, beta)=(8,-6):

9171 -> 7452 -> 4905 -> 189 -> 9621 -> 8352 -> 5814 -> 1629 -> 7632 -> 5265 -> 360 -> 270 -> 450 -> 90

All in all, this approach looks better than computing all F(.) sequences for all N's, but would still require a lot of computations and reasoning.

I did not find a more "interesting" way of deducing the result.

[Guest]

That's some good work araver!

Yes, in some instances, it is simply much easier to show the result "by inspection" rather than bother with an analytical proof. I'm hoping to reduce the need for this signicantly more than what you've given so far though. There is such a strong pattern across all of these numbers, I feel it should be more than just random.

Unfortunately, as I was looking through my proof before posting it here, I found a critical error. I'm still going to post it though (with the error highlighted), as I think the general approach might help someone else find a solution.

Definitions:

I start with N, expressed in four digits by a b c d.

For ease of communication, I'll refer to representing a number by its individual digits in this manner as its "digital" form.

x = a-d

y = b-c

As we're only interested in absolute values, we can consider x > 0 without loss of generality.

Proof:

Firstly, we can see "by inspection" that the proposition holds true for single digit multiples of 90, 999, and 1089 (there's probably a simple proof for this, but for just 10 multiples of each,its not worth it IMHO). Also, it is clear that multiples of 909 must be palindomic. Thus, if we can show that by repeadetly applying F(), any N can be reduced to a multiple of these numbers, then the proposition is proved.

Further, we know that for any non-palindromic N, F(N) can be expressed as follows:

999x + 90y (see araver's solution to problem for an explanation)

By writing the number in this form, we see clearly that for the following cases, F(N) is divisible by either 90, 909, 999, or 1089:

x = 0

y = 0

x = y

x = -y

For all other cases:

I want to express 999x + 90y in digital form.

Step 1: 999x in digital form is: (x-1) 9 9 (10-x)

Step 2: 90y in digital form is 0 (y-1) (10-y) 0

Writing these out as a standard arithmetic sum:

      (x-1)      9     9     (10-x)

plus     0    (y-1)  (10-y)    0

Adding one column at a time: Units column: 10-x+0 = 10-x 10s column: 9 + 10 - y = 9 - y (with 10 carried over) 100s column: 1 (carried over) + 9 + y - 1 = y - 1 (with 10 carried over) 1000s column: 1 (carried over) + x - 1 = x Thus, F(N), in digital form, is x (y-1) (9-y) (10-x) Now reversing this and subtracting (we're interested in absolute values again, so assuming x>10-x):

	  x    (y-1)    (9-y)	(10-x)

minus   (10-x) (9-y)    (y-1) 	   x

Using the same "column by column" arithmetic, we get the answer as:

1000(2x-10) + 100(2y-10) + 10(10-2y) +(10-2x)

= 999(2x-10) + 90((2y-10)

This is of the same form as before, so my proof relied on the fact that the function abs(2x-10), when performed repeatedly, converges to a cycle of 2,6. I then showed that for the four combinations of x,y=2,6, the proposition held true.

Unfortunately, I now relise this proof has a flaw. The mistake is in my calculation of the digital form for F(N). While adding the columns, I have implicitly assumed y>0. If y<0, then F(N) in digital form comes out as: (x-1) (10-y) (y-1) (10-x), and when the reverse of this number is subtracted, the final result is: 999(2x-11) + 90(11-2y).

This series is much more difficult to model, as there is now interaction between the x and y terms (depending on the sign of 11-2y or 2y-10), and the absolute value maths is trickier. Even after doing so however, it does not converge to a simple solution. The series is cyclical, but the number of potentail x,y combinations is only a small improvement on just using all x,y combinations between -9 and 9 to begin with.

I'm still working on another proof, but thought I'd post this up incase it gives someone else food for thought.