# Number Theory: Chinese Rem. Thm. - Designing a numbering system

1. Feb 19, 2007

### mattmns

Here is the exercise from the book:
--------
You are asked to design a system for numbering TV programs to facilitate the programming of VCRs. Each program should be assigned a number so that a VCR can determine the day of the week, starting time, ending time and the channel of the program. The system should be efficient, that is, use as few numbers as possible, and also easy to implement using a computer. Assume there are a maximum of 100 channels, and programs can begin and end in time units that are multiples of 15 minutes. Design a number system using these criteria. What percentage of the total possible numbers are actually used?
--------

This is in the section on the Chinese Remainder Theorem, so something with mods and systems of congruences should be expected.

Let n be our number that holds all the information.

For the days of the week, I thought simply we would want n mod 7. Where 0 mod 7 was Saturday, 1 mod 7 Sunday, and so on.

Then I thought why not n mod 100 for the channels. 0 mod 100 for channel 0, 1 mod 100 for channel 1 and so on. Seems good.

Now the timing part is what I am having trouble with.

First should I assume that you can only record consecutively for say less than a day?

The reason I say this is that I am not sure how we could have a starting day and time, and an ending day and time (since I would think they would have to both have the same number mod 7, and for the time as well). So I have been trying to break it up into starting time, and duration of recording.

So I say there are 96 = ($4\cdot 24$) times you can start a program in a given day (for every 15 minute interval in a day).

But now for some reason I cannot figure out how to make a duration. Which is where I think the max length of duration would need to come in. If we had no max duration, then we would never be able to say a program ended. So I want 15minutes to be 1 mod something, 30minutes to be 2 mod something, and so on. I was thinking of having say mod 99 for example. And then having 1 mod 99 mean 15 minute program, 2 mod 99 be a 30 minute program. This assumes though that the max amount of time you can record is $15\cdot 99$ minutes, which is never stated in the exercise.

Assuming all this is correct (I would maybe want to change 99 so that applying the Chinese remainder theorem would be easier?). Then I need to find a numbering system? First, what is a numbering system? Our book has never defined or talked of such a thing. I am guessing it is just a set of numbers that have some relationship with the given criteria? If so, why not just define the set to have a unique map to all the different possible television programs/times/dates/durations. Thus making the percentage of numbers used 100% (I am guessing this might be difficult to do, and the author wants us to come up with some simple set of numbers?).

I guess this is kind of a long read, but for those that have read this far, do you have any ideas or insight into the problem? Thanks!

2. Feb 21, 2007

### mattmns

<bump> Any ideas at all?