A database stores every ordered pair of natural numbers as one natural-number code. The code is given by ,
For example, and . Which statement about is correct?
Confirming your payment
Competency-Based Questions (CBQ) · Question 59 of 80
A database stores every ordered pair of natural numbers as one natural-number code. The code is given by ,
For example, and . Which statement about is correct?
(A) is one-one but not onto, and the pair with code is
(B) is onto but not one-one, since the code comes from more than one pair
(C) is a bijection, and the pair with code is
(D) is a bijection, and the pair with code is
Option (D) is correct.
The whole question rests on one fact: every natural number can be written as
in exactly one way. Keep halving until the result is odd. The number of halvings is , and what is left is the odd part.
Step 1: is one-one. Suppose , that is . If , divide both sides by :
The left side is even and the right side is odd, which is impossible. In the same way is impossible. So . Cancelling then gives , so . Hence .
Step 2: is onto. Take any and write with odd. Put and . Both are natural numbers (since and is odd), and .
So is a bijection.
Step 3: the pair with code . Halve : . That is three halvings, and the odd part is . So , which gives and , that is
Check: .
The table shows the first few codes. Every row is a power of times the odd numbers , so no code appears twice.
Why the other options are wrong