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 is a bijection such that if and , then .

Prove that if then .

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

Note that the -th column contains as many elements as the number of divisors of . Now we just just use a simple observation. Let be on the -th column (i.e. ). If then cannot be on one of the first columns. Indeed, the monotonicity property implies . The fact that is a bijection assures us that cover the first columns. Moreover, one element from the -th column is surely covered, namely . This means that

where we have denoted by the number of positive divisors of .

Advertisements

Categories: Algebra, Number theory, Olympiad
Algebra, monotone, number theory, olympiad, trick

Comments (0)
Trackbacks (0)
Leave a comment
Trackback