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 »
 Pages: 1 Reply Notify of replies Send Topic Print
 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.

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)
 Pages: 1 Reply Notify of replies Send Topic Print

 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 »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board