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

Given that $(0,0)$ $\epsilon$ $P$.

And a pair $(a,b)$ will be in $P$ if $amod10$ is less than or equal to $bmod10$ and if $(a/10, b/10)$ is in $P$

Here $\leq$ is the mathematical operator and not the symbol that denotes a relation in POSET.

---

$(101,22)$

1 $\leq$ 2 True. And does  $(10,2)$ $\epsilon$ $P$?

0 $\leq$ 2. True. And does $(1,0)$ $\epsilon$ $P$?

1 $\leq$ 0. False.

So $(i)$ does not belong to P.

 

Options A and C eliminated.

---

If $(ii)$ is True then B is the answer. If not, then D is the answer. So check $(ii)$

$(22,101)$

2 $\leq$ 1. False.

---

So Option D

Comments

Yes, it’s right. But how we will come to know whether we have to do recursively or not :(

@Arjun  @Bikram Sir please help.

Answer 2

How could 0 belong to P, 0 isn't even natural number. @sachin_mittal @Arjun

Answer 3

In this problem.

a % b means the mod function (i.e residue when a is divided by b).

a/b means integer division (i.e quotient when a is divided by b)

i)   (101,22):

101% 10 ≤    22% 10

1≤ 2 which is true.

(101/10, 22/10)

(10, 2)∊  P need to check is  (10, 2) ∊ P

10% 10 ≤ 2% 10  

0 ≤2 which is True.

Then (10/10, 2/10)= (1, 0) fails since . (101, 22) not belongs to  P

(ii) (22, 101)

22% 10 ≤ 101% 10

2 ≤ 1 is False.

 (22, 101) not belongs to P

(iii) (145, 265)

145% 10 ≤ 265 % 10

5 ≤ 5 is true and (145/10, 265/10) = (14, 26) ∊ P has to be checked. Now consider (14, 26).

14% 10 ≤ 26% 10

4 ≤ 6 is true and (14/ 10, 26/10)= (1, 2) ∊ P has to be checked. Now consider (1, 2) 1% 10 ≤ 2% 10 15 2 is true and (1/10, 2/10)=(0, 0) ∊ P which is given to be true. Therefore (145, 265) ∊ P

(iv) (0, 153):

0% 10 ≤ 153% 10⇒  0 ≤ 3 is true

Then (0/10, 153/10)= (0, 15) should be in P (0,15):

0% 10 ≤ 15% 100 ≤ 5 is true.

Then (0/10, 15/10)= (0, 1) should be in P

(0, 1): 0% 10 ≤ 1% 100 ≤ 1 is true.

Then (0/10, 1/10)= (0, 0) should be in P It is given that (0, 0) ∊ P

Therefore (0, 153) ∊ P So (ii) and (iv) are contained in P