Is there any pairing function that could encode two positive, natural numbers, with values ranging from $0$ to $3000$, into a single natural number with a value less or equal to $65535$?
Pairing function
3
$\begingroup$
functions
1 Answers
6
No, a simple counting argument rules out such a map.
For any $n \geqslant 0$, denote by $[n]$ the set $\{0, 1, \ldots, n\}$. The set $[3000]^2$ is of size $3001^2 \gt 9 \times 10^6$, whereas the size of $[65535]$ is $65536$ which is strictly smaller than $9 \times 10^6$. So by the pigeonhole principle, there does not exist a surjective an injective (one-to-one) map from $[3000]^2$ to $[65535]$.
EDIT: I am assuming that the pairs are ordered. Even if we count only the unordered pairs, the same conclusion follows. Note that the number of unordered pairs is $\binom{3002}{2} \geqslant 4.5 \times 10^6$, which is also larger than $65536$.
-
0@Ross, I added that variation in the answer. Thanks for pointing it out. – 2011-11-15