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

for third (1645,245), how is 145%10 <265 %10 they are same as both are 5

---

I think < must be ≤ in question.

---

yes ur correcta Arjun!

---

yes, it is ≤ in the actual question.

---

Why not 101,22

---

Original question was with simply < condition. (Please correct the questions)

(a, b) ∊ P if and only if a % 10 < b % 10 and (a/10, b/10) ∊ P

(i) (101,22) is in P :

        Reason:   101%10 < 22 %10 implies 1 < 2 is true

                          and (101/10, 22/10) = (10,2) should be in P, So we should verify (10,2) pair : (10%10 < 2%10)  implies 0 < 2 is true and (10/10, 2/10) = (1,2) is in P. So pair (101, 22) is in P

(ii) (22, 101) is not in P:

        22%10 < 101%10 implies 2 < 1 is false. Therefore (ii) is not in P.

(iii) (145, 265) is not in P:  

          145 %10 < 265 %10 implies 5 < 5 is false. Therefore (iii) is not in P.

(iv) (0, 153) is in P :

        Reason:   0%10 < 153 %10 implies 0 < 3 is true

                          and (0/10, 153/10) = (0, 15) should be in P, So we should verify (0,15) pair: (0%10 < 15%10)  implies 0 < 5 is true and (0/10, 15/10) = (0,1) is in P. 

       So pair (0, 153) is in P

Answer is (i) and (iv) : Option (C) is correct.

---

but (10/10, 2/10) = (1,0) and not (1, 2) and hence not in P

---

≤ can be seen if we look very carefully in the question here. Unfortunately I couldn't find a better source. 

http://www.examrace.com/GATE/GATE-Previous-Years-Papers/Information-Technology/GATE-Information-Technology-2007.html#pdfsection_ef89c298-page_3-locus_73

---

very nice.. Yes it should be less than or equal.. Thank you

---

why option (i) 101,22 is not correct ?

---

Why options i is not correct?

---

is there any significance to specifying "partial order"? I feel, even if it was not partial order, but just a simple relation, then even the solution would have been same, right?

---

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 ??