wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Integer Generation
        
(Message started by: william wu on Oct 12^th, 2002, 11:07pm)

Title: Integer Generation
Post by william wu on Oct 12^th, 2002, 11:07pm

Here's a problem a friend gave me recently. I told him I was feeling bored, so he gave me a math problem :P

Consider the following method for generating integers:

1. If I have an integer pair (x,y), I can generate (x+1,y+1).
2. If I have the pairs (x,y) and (y,z), I can make (x,z).
3. If I have (x,y) and both x and y are even, then I can make (x/2, y/2).

Given some initial integer pair (a,b), you can generate a whole bunch of other integer pairs.

Show that if you start with (7,29), you can't generate (3,1999).

Title: Re: Integer Generation
Post by Pietro K.C. on Oct 13^th, 2002, 9:41am

Cool one... model theory. :)

If you assume that x,y are always integers, then these rules are very similar to what can be done with modular arithmetic. You just take (x,y) to mean x = y (mod m) for some appropriate number m (not even, because of rule 3).

In this case, since 29-7 = 2*11, I set m=11. Then, starting from (7,29), I can only achieve pairs (x,y) such that 11 divides x-y. Because, in getting to (x,y), I used one of the 3 rules on a previous pair (u,v) (and possibly another, (v,w)); if u-v and u-w were divisible by 11, then

x - y = (u+1) - (v+1) = u-v,
x - y = u - w = (u-v) + (v-w),
x - y = u/2 - v/2 = (u-v)/2

are all divisible by 11.

And since 3 - 1999 = -1996 = 6 (mod 11), the pair (3,1999) can never be reached starting with (7,29).