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

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: