wu :: forums
wu :: forums - Integer Generation

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 3:50pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Integer Generation  (Read 758 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Integer Generation  
« on: Oct 12th, 2002, 11:07pm »
Quote Quote Modify Modify

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





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Integer Generation  
« Reply #1 on: Oct 13th, 2002, 9:41am »
Quote Quote Modify Modify

  Cool one... model theory. Smiley
 
   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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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