wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> (Double, Increment) Transformation
        
(Message started by: Barukh on Sep 21^st, 2004, 4:01am)

Title: (Double, Increment) Transformation
Post by Barukh on Sep 21^st, 2004, 4:01am

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.

Title: Re: (Double, Increment) Transformation
Post by Aryabhatta on Sep 22^nd, 2004, 2:34pm

Interesting problem Barukh.

Here is an attempt. I am sure other solutions won't be as ugly as this.
[hide]

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, 2^D(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

( 2^a(x+D), 2^D(x+D) + a )

Now double the second number once.
( 2^a(x+D)+1, 2^D+1(x+D)+2a )

Now double the first number b+1 times.

( 2^D+1 (x+D) + 2^b+1,2^D+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 = 2^D+1(x+D)

So assume D > 3.

D' = first number - second number

D' = 2^b+1 - 2a - b -1
Since b = [log D] we have that

2^b [le] D

So D' [le] 2D - (a+b) - a - 1 = D-1 - a = b-1 < D -1

Also
2^b+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.

[/hide]
::

Title: Re: (Double, Increment) Transformation
Post by Aryabhatta on Sep 24^th, 2004, 8:32am

on 09/21/04 at 04:01:55, Barukh wrote:

What solution did you have in mind, Barukh? I am dying to know a good solution to this.

Title: Re: (Double, Increment) Transformation
Post by Barukh on Sep 25^th, 2004, 1:01am

on 09/24/04 at 08:32:18, 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).