A partial order P is defined on the set of natural numbers as follows. Here…
2007
A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
i. (0, 0) ∊ P.
ii. (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P.
Consider the following ordered pairs:
i. (101, 22)
ii. (22, 101)
iii. (145, 265)
iv. (0, 153)
Which of these ordered pairs of natural numbers are contained in P?
- A.
(i) and (iii)
- B.
(ii) and (iv)
- C.
(i) and (iv)
- D.
(iii) and (iv)
Attempted by 148 students.
Show answer & explanation
Correct answer: D
Key idea: The relation holds exactly when every corresponding decimal digit of the first number is less than or equal to the corresponding decimal digit of the second number, checking from the least significant digit upward and terminating at (0,0).
Check (101, 22): units: 1 ≤ 2 (ok); then (10, 2): tens: 0 ≤ 2 (ok); then (1, 0): hundreds: 1 ≤ 0 (fails). Therefore (101, 22) is not in P.
Check (22, 101): units: 2 ≤ 1 (false). The relation fails immediately, so (22, 101) is not in P.
Check (145, 265): units: 5 ≤ 5 (ok); tens: 4 ≤ 6 (ok); hundreds: 1 ≤ 2 (ok). All digitwise comparisons hold and we reach (0,0), so (145, 265) is in P.
Check (0, 153): units: 0 ≤ 3 (ok) giving (0,15); then 0 ≤ 5 (ok) giving (0,1); then 0 ≤ 1 (ok) giving (0,0). Thus (0, 153) is in P.
Answer: The ordered pairs in P are (145, 265) and (0, 153).
A video solution is available for this question — log in and enroll to watch it.