Associated Topics || Dr. Math Home || Search Dr. Math

### 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

Thanks,
Siamak
```
Associated Topics:
High School Analysis
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search