Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This may have more to do with computing than Mathematics in its application, however this has been giving me a headache for some time and I see no other recourse than to ask...

Given a natural integer T > 9 (and probably between 1,000 and 1,000,000,000), and a choice N in {0,1,2,3,4}, provide two algorithms (encoding and decoding):

  • One which take T and N as inputs and outputs R, a number which has no more digits than T. [encoding]

  • The other which takes an (encoded) number R and outputs the original (unencoded) T and N. [decoding]

The complexity of the algorithms should at best allow to be implemented by modern computing. Apart from that, everything and anything is allowed :).

As a side note, do advise me if this is impossible.

share|improve this question
    
What is N supposed to do in both algorithms? –  J. M. Dec 20 '10 at 10:36
    
The problem is one of computing and I will not go into these details here. Basically, one must encode T and N together such that the result R is no longer than T and that T and N can be retrieved later from R uniquely. –  Félix Saparelli Dec 20 '10 at 10:41
    
See also the closely related question math.stackexchange.com/q/3419/242 –  Bill Dubuque Dec 20 '10 at 14:32

1 Answer 1

up vote 6 down vote accepted

This is impossible for the same reason a compression algorithm that reduces the size of every file is impossible. Suppose $T$ has $k$ decimal digits. There are $9\times10^{k-1}$ possible values of $T$, and $5$ possible values of $N$, making $45\times10^{k-1}$ possible $(T,N)$ pairs. But since you're only allowed up to $k$ digits in $R$, there are only $10\times10^{k-1}$ possible values of $R$ to encode them in. So no matter what you do, you won't be able to decode $R$ back into $T$ and $N$.

share|improve this answer
    
Yes, that's what I thought. I started playing with factorials and saw a compression possibility... however it seemingly will not work on small numbers and I do not have the time to either prove it or leave my computer running to compute an example on large (>10^16) numbers. Thanks! –  Félix Saparelli Dec 20 '10 at 10:54
    
@passcod: The same argument works for any number of digits. See my edited answer. –  Rahul Dec 20 '10 at 11:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.