Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, 45$ will come and chain will repeat. from any number we will enter in this chain.

Can anyone help me to prove this?

share|improve this question
    
I am not sure if this is merely misunderstanding on my part: $x=8,y=9, 10x+y = 89, + y-x = 90$. But ninety isn't an element of your chain –  Display Name Apr 20 at 12:04
1  
Satvik: What is your source? –  Did Apr 20 at 12:13
3  
I graphed the iteration of your function, and noticed an interesting symmetry. It seems that that the mapping $x\to99-x$ is an "automorphism" for this function: $f(99-x)=99-f(x)$. –  Jack M Apr 20 at 12:29
2  
Note that the function doubles the value modulo $11$. Since $2$ is a primitive root modulo $11$, it suffices to check all numbers of the form $11k$ or $11k+1$. The numbers $11k$ are explicitly excluded, so we just have to check for example $12,23,34,45,56,67,78,89$. –  barto Apr 20 at 12:45
2  
@KarlKronenfeld You're mapping $10x+y$ to $9x+2y$. Look at it modulo $11$. You have $9x+2y=0$, and note that $9=-2$. –  Jack M Apr 20 at 12:45

2 Answers 2

up vote 26 down vote accepted

First of all, you must check that this process stays inside $\{1...99\}$. At each stage the iterated function $f$ adds a number between $0$ and $9$, so in order to have $f(x)>99$, we would need $x>90$. But for $x>90$, the units digit is always smaller, so you're always adding a negative value. Similarly, to have $f(x)<1$, we would need $x<10$, but then the units digit is always bigger, so you always add a positive value.

So, since we always stay within that finite set, we must get a repetition eventually. As soon as that happens, we'll enter a cycle. We have only to verify that the one you describe in your question is the only one. This can be checked explicitly by getting a computer to calculate $f(x)$ for $1\leq x\leq 100$:

Bigger image. Sorry about the messy graph, couldn't find good plotting software.

I somewhat doubt there's any more profound proof than that. It's a fairly arbitrary mapping as far as I can see. The fact that it will eventually repeat is something common to all mappings of a finite set to itself. Some of those mappings have $3$ cycles. Some have $18$. This one happened to have $1$. Sure, why not. Or, to put it another way, the non-trivial feature of your function is that it maps $\{1, ... 99\}$ into itself, and the cycle is just a corollary of that.

What I do find interesting is the symmetry of the above graph. It could be explained if we could prove that:

$$f(99 - x) = 99 - f(x)$$

That is, the involution $x\to99-x$ is an automorphism for this system (not sure if the word "automorphism" is actually used in this context, but if nothing else it's certainly an automorphism of the above directed graph). This is because this involution has the effect of replacing each digit in a two-digit number with $9$ minus itself, so $10x+y$ gets mapped to $10(9 - x) + (9 - y)$. So the difference between the two digits changes from $y-x$ to $(9-y)-(9-x)=x-y$, that is, it gets multiplied by $-1$. So if $x$ is a two digit number and $f(x)=x+d$, we have:

$$99-f(x)=99-(x+d)=(99-x)-d=f(99-x)$$

share|improve this answer
11  
All roads lead to Rome. Or in this case, to $45$. –  Asaf Karagila Apr 20 at 13:52
4  
Nice picture! (+1) –  O.L. Apr 20 at 14:01
1  
Consider graphviz –  vonbrand Apr 20 at 14:04
3  
Here are the graphs drawn using graphviz clearly showing the symmetry. They're drawn using the neato and twopi algorithms. One looks like a flying tree frog: static.rcgroups.net/forums/attachments/2/6/7/7/4/4/… , static.rcgroups.net/forums/attachments/2/6/7/7/4/4/… –  slebetman Apr 21 at 4:56

Here are some thoughts that make it possible to understand what is going on without much computation.

First, your transformation is compatible with reduction modulo$~11$, for which it gives the operation of multiplication by$~2$, as one has $10x+y\equiv y-x\mapsto10x+y+(y-x)\equiv2(y-x)$. Since you forbade the multiples of$~11$, and $2$ happens to be a generator of the multiplicative group $(\Bbb Z/11\Bbb Z)^\times$, all values give the same repeating cycle of$~10$ nonzero congruence classes modulo$~11$, started at different points.

To understand the precise behaviour, consider a set of $10$ successive values $\{11n-10,\ldots,11n-1\}$ for a fixed $0<n<10$. The amount added to these numbers increases going from $11n-10$ up to $10n-1$, then drops (by$~10$) for $10n$ after which it increases when continuing to $11n-1$. Therefore if any number in this set maps to a number larger than any in the set, then it certainly happens to $10n-1$, and if any number in this set maps to a number smaller than any in the set, then it certainly happens to$~10n$. But the former happens whenever $10n-1+(9-(n-1))>11n-1$ which amounts to $n<5$, while the latter happens whenever $10n+(0-n)<11n-10$ which amounts to $n>5$. In particular both conditions are mutually exclusive, and one of them happens (the set "leaks" upwards or downwards) unless $n=5$. Now it is clear that for $n=5$ one obtains the only nonempty set of allowed numbers that is mapped bijectively to itself, and it is therefore the only possible final cycle.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.