Home > Algebra, Number theory, Olympiad > Monotonic bijection from naturals to pairs of natural numbers

## Monotonic bijection from naturals to pairs of natural numbers

This is a cute problem I found this evening.

Suppose ${\phi : \Bbb{N}^* \rightarrow \Bbb{N}^*\times \Bbb{N}^*}$ is a bijection such that if ${\phi(k) = (i,j),\ \phi(k')=(i',j')}$ and ${k \leq k'}$, then ${ij \leq i'j'}$.

Prove that if ${k = \phi(i,j)}$ then ${k \geq ij}$.

Proof: The trick is to divide the pairs of positive integers into families with the same product.

$\displaystyle \begin{matrix} (1,1) & (1,2) & (1,3) & (1,4) & (1,5) & (1,6) & \cdots \\ & (2,1) & (3,1) & (2,2) & (5,1) & (2,3) & \cdots \\ & & &( 4,1) & & (3,2) & \cdots \\ & & & & & (6,1) & \cdots \end{matrix}$

Note that the ${M}$-th column contains as many elements as the number of divisors of ${M}$. Now we just just use a simple observation. Let ${\phi(k)=(i,j)}$ be on the ${M}$-th column (i.e. ${ij = M}$). If ${n \geq 1}$ then ${\phi(k+n)=(i',j')}$ cannot be on one of the first ${M-1}$ columns. Indeed, the monotonicity property implies ${M = ij \leq i'j'}$. The fact that ${\phi}$ is a bijection assures us that ${\phi(1),...,\phi(k)}$ cover the first ${M-1}$ columns. Moreover, one element from the ${M}$-th column is surely covered, namely ${(i,j) = \phi(k)}$. This means that

$\displaystyle k \geq d(1)+...+d(M-1)+1 \geq M = ij,$

where we have denoted by ${d(n)}$ the number of positive divisors of ${n}$.