3
$\begingroup$

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

1 Answers 1

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