Author |
Topic: Integer Generation (Read 784 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Integer Generation
« on: Oct 12th, 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 13th, 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 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).
|
|
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)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print