wu :: forums « wu :: forums - Integer Generation » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 3:50pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  putnam exam (pure math) (Moderators: william wu, towr, Eigenray, Icarus, Grimbal, SMQ)  Integer Generation « Previous topic | Next topic » Author Topic: Integer Generation  (Read 758 times)
william wu       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. 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)

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »