0
$\begingroup$

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.

  • 0
    What is `N` supposed to do in both algorithms?2010-12-20
  • 0
    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.2010-12-20
  • 0
    See also the closely related question http://math.stackexchange.com/q/3419/2422010-12-20

1 Answers 1

6

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$.

  • 0
    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!2010-12-20
  • 0
    @passcod: The same argument works for any number of digits. See my edited answer.2010-12-20