GATE IT 2007 | Question: 23

Question

A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division.

1. $(0, 0) \in P.$
2. $(a, b) \in P$ if and only if $(a \% 10) \leq (b \% 10$) and $(\frac{a}{10},\frac{b}{10})\in  P.$

Consider the following ordered pairs:

1. $(101, 22)$
2. $(22, 101)$
3. $(145, 265)$
4. $(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)

Comments

How we will know we have to do it recursively as it's nowhere mentioned In question or should we use smes extra brain thinking that 101/10 and 22/10 gives (10,2) and can (10,2) be part of relation? Well no coz 10%10 and 2%10 gives (1,2) which fails first condition.

---

But P is defined on the set of natural numbers

---

Is the Question itself trying to explain Partial Order (P) by giving the condition:

1. (0,0)∈P.(0,0)∈P.
2. (a,b)∈P(a,b)∈P if and only if (a%10)≤(b%10(a%10)≤(b%10) and (a10,b10)∈P.

If both satisfy then it’s Partial Order else not?

Answer 1

Ans. D
For ordered pair $(a, b),$ to be in $P,$ each digit in a starting from unit place must not be larger than the corresponding digit in $b.$

This condition is satisfied by options

• (iii) $(145, 265) \to 5 ≤ 5, 4 < 6$ and $1 < 2$
• (iv) $(0, 153) \to 0 < 3$ and no need to examine further

Comments

how to do ypu understand % is modulus not divide operator?

---

@Vikrant How do we know that computing a%10 and b%10 is iterative (doing it till number becomes 0) since it is not explicitly mentioned in the question?

---

@shetu_raj for (101,22) to belong to P, 101/10(=10) & 22/10(=2) should belong to P, for (10,2) to belong to P we repeat the similar process

Answer 2

it is just like recursion for more understandbility we hve following ideas as.

We will have to check each and every condition recursive untill condition become completed.

Now check for (145,265)      a%10<=b%10 now remaining(14,26) again check a%10<=b%10 yes again check .

Similraly u can apply for option four .

Answer 3

(i)      (101, 22)

                 |

    -----------------

      |                |

   (1,2)         (10,2)

                      |

            --------------

              |              |

           (0,2)         (1,0)  ---> fails here bcz (a !<= b)

likewise you can check other options.

(iii) & (iv) are correct, hence option D    

Answer 4

Since P is given to be a partial order relation, options (i) & (ii) are ruled out as they violate  antisymmetry which says that if (a,b)∊R & (b,a)∊R => a=b but 22 ≠101.

Now 145%10≤265%10 and the evaluating the second condition gives (0,0) which is given to be in P. In similar vein (iv) can also be checked to be in P. 

Hence option iii & iv is correct.

Comments

@Aman_verma
145 ≠ 265

0≠153

Does it also violate asymmetric conditions ??