Set Notation via Broken TypewriterDate: 11/19/2002 at 03:15:17 From: Siamak Subject: Honors Math Analysis I am enrolled in an honors Math Analysis course and the teacher assigned a "classic problem." It is as follows: I have a machine that only types out ones (no spaces or tricks involved). What procedure must you do to this machine to get any given finite set? For example [2,85,11,5,60]. For a different set, the number of ones that the machine types out will vary. I tried looking at the ones in binary notation but that doesn't seem to work since you can't have any zeros. She said to think simply, and that for each different set, the number of ones would vary. So, just by looking at the group of ones, she would be able to tell what the set is. I am completely lost.. Please suggest any method I might use to approach this problem. Date: 11/22/2002 at 16:02:53 From: Doctor Shawn Subject: Re: Honors Math Analysis Siamak, This is a pretty tricky problem. The only way that I know how to do it is fairly elegant but gets VERY impractical very quickly. I'll give you two clues to get you started: There's only one way to factor any given number into primes. Start at the beginning and move onward. The problem is that it's difficult to convey information like this. If you send a piece of paper with four ones on it, is that the number four, or four ones, or a one and a three? I'm sure this has been bugging you as well. You just have to come up with an algorithm where both you and the sender can be clear about what you're sending. When I told you that each number only has one prime factorization, that was a hint: Suppose the set is [4]. 2 is the smallest prime number, so you multiply it together 4 times (2^4 = 16). You send 16 ones on the piece of paper, and then the recipient on the other end factors out the number, and knows that you meant 4 and only 4. Now, suppose the set is [3 2]. We'll need both 2s and 3s this time: 2^3 * 3^2 = 72. So send 72 ones on the piece of paper, and after factoring it, your recipient will realize that you meant 3, then 2. But there are complications. There is the issue of negative integers, decimals, and zero. This is not an insoluble dilemma; I'll give you a hint as to this part of the problem: sometimes you just have to skip some prime numbers. Try that out for a while, and if you need a last push, write again. - Doctor Shawn, The Math Forum http://mathforum.org/dr.math/ Date: 11/23/2002 at 18:36:39 From: Siamak Subject: Honors Math Analysis Wow. That makes things so much simpler. Now I think I know how to indicate negatives, zero, and decimals, based on your clue, but I'm not really sure. For negatives, skip one prime number. For zero, skip two prime numbers, and for decimals, skip three prime numbers. So for the set [ -3, 0 , 0.7] you would do 3^3 * 7 * 17^7. But I think this method is too complicated because I don't know how to include numbers like 4.7, and if you want to combine a negative and a decimal, you have to skip five prime numbers. Is there an easier way? Date: 11/23/2002 at 19:10:21 From: Doctor Shawn Subject: Re: Honors Math Analysis Siamak, I don't think I'd describe it as too complicated - this is more of a thought experiment than anything. I mean, if you have large numbers or a long list of numbers, the number of 1s you're sending on the piece of paper rapidly becomes large beyond all management. The key is just that it _works_. Your method is almost there, but not quite. Suppose you have a zero, then a negative number? You wouldn't be able to tell the three skips from a decimal point. The method I had in mind earlier wouldn't have worked out very well, but I think I've solved it now (and please, if you spot a flaw in this, correct me.) Here are the rules: For a negative sign, skip one prime number. For a zero, skip four prime numbers. Decimals are a little tricky, but we'll specify to our recipient that a decimal number will never end in zero. For a number like .5, we'll skip two prime numbers, send the 5, and then skip two more to show that it's closed. For a number like 4.5, we'll skip two primes to start, send 4, skip 1 prime, send the 5, and then skip two more to show that it's closed, or in other words: Skip two primes to start a decimal number and two more when you're done. Zeroes never go at the end of a decimal number, and a skip of one prime between two skips of two is a decimal point. If there is no skip of one, then the decimal goes at the beginning of the number. I'm pretty sure that works. If you can play around with it a bit and manage to send something ambiguous, please let me know! - Doctor Shawn, The Math Forum http://mathforum.org/dr.math/ Date: 11/23/2002 at 22:13:16 From: Siamak Subject: Thank you (Honors Math Analysis) Doctor Shawn, It's perfect! Thank you so much for helping me solve this problem. I truly appreciate the time you spent to explain the problem and I am glad to say that I had fun with it. I really appreciate all your help. Thanks, Siamak |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/