Author |
Topic: (Double, Increment) Transformation (Read 526 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
(Double, Increment) Transformation
« on: Sep 21st, 2004, 4:01am » |
 Quote  Modify
|
On a pair of natural numbers (x, y), the transformation is performed that doubles one number, and increments the other. For instance, the pair (2, 5) may be transformed into (4, 6) or (3, 10).
Prove that any pair may be transformed into a pair of equal numbers by repeatedly applying this transformation.
Source: Prof. O. Kryzhanovsky.
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: (Double, Increment) Transformation
« Reply #1 on: Sep 22nd, 2004, 2:34pm » |
Quote Modify
|
Interesting problem Barukh.
Here is an attempt. I am sure other solutions won't be as ugly as this.
Basic idea is to reduce the difference D between the two numbers, i.e when numbers are x and x+D.
D = 2 turned out to be easier than D = 1.
( x , x+2 )
( x+2, 4x+8 ) [Double 2nd number twice]
( 2x+4,4x+9)
( 2x+5,8x+18 )
( 4x+10,8x+19 )
( 8x+20,8x+20 ) !
The case D = 1 can be 'reduced' to the case D = 2.
( x, x+1 )
( x+2,4x+4 )
( 4x+8,4x+6 )
Now consider the case D > 2. We would like to show that we can reduce the difference. It took me a while before I figured out the following sequence... I am sure there must be a better way.
We have ( x, x + D )
Double the second number D times.
( x+D, 2D(x+D) )
Let D = a + b where b = [log D] (log is to the base 2)
(and [t] is integral part of t)
Now double the first number a times
( 2a(x+D), 2D(x+D) + a )
Now double the second number once.
( 2a(x+D)+1, 2D+1(x+D)+2a )
Now double the first number b+1 times.
( 2D+1 (x+D) + 2b+1,2D+1(x+D)+2a+b+1 )
For the case when D=3, a=2 and b=1 we have
(M+4,M+6) where M = 2D+1(x+D)
So assume D > 3.
D' = first number - second number
D' = 2b+1 - 2a - b -1
Since b = [log D] we have that
2b [le] D
So D' [le] 2D - (a+b) - a - 1 = D-1 - a = b-1 < D -1
Also
2b+1 > D
So
D' > D - (a+b) - a - 1 = -a - 1 [ge] 1 - D for D > 3.
So |D'| [le] D-1
So we reduce the difference repeatedly and get it to 1 or 2.
It might be interesting to see if we can find optimal ways to equalise the numbers.
::
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: (Double, Increment) Transformation
« Reply #2 on: Sep 24th, 2004, 8:32am » |
Quote Modify
|
on Sep 21st, 2004, 4:01am, Barukh wrote:On a pair of natural numbers (x, y), the transformation is performed that doubles one number, and increments the other. For instance, the pair (2, 5) may be transformed into (4, 6) or (3, 10).
Prove that any pair may be transformed into a pair of equal numbers by repeatedly applying this transformation.
Source: Prof. O. Kryzhanovsky. |
|
What solution did you have in mind, Barukh? I am dying to know a good solution to this.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: (Double, Increment) Transformation
« Reply #3 on: Sep 25th, 2004, 1:01am » |
Quote Modify
|
on Sep 24th, 2004, 8:32am, Aryabhatta wrote:What solution did you have in mind, Barukh? I am dying to know a good solution to this.
|
|
I have to disappoint you, Aryabhatta: all the solutions I'm aware of, are based on the same idea, and are as"good" as yours. Please look at your private messages: I will send you a link (which, of course, I will make public later).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print