Set Notation via Broken Typewriter

Date: 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