Author 
Topic: Integer Generation (Read 758 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Integer Generation
« on: Oct 12^{th}, 2002, 11:07pm » 
Quote Modify

Here's a problem a friend gave me recently. I told him I was feeling bored, so he gave me a math problem 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).


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Integer Generation
« Reply #1 on: Oct 13^{th}, 2002, 9:41am » 
Quote Modify

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 297 = 2*11, I set m=11. Then, starting from (7,29), I can only achieve pairs (x,y) such that 11 divides xy. 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 uv and uw were divisible by 11, then x  y = (u+1)  (v+1) = uv, x  y = u  w = (uv) + (vw), x  y = u/2  v/2 = (uv)/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).


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



