562 views

A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.

1. (0, 0) ∊ P.
2. (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ 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?

1. (i) and (iii)
2. (ii) and (iv)
3. (i) and (iv)
4. (iii) and (iv)
@Arjun Sir, What is the correct ans ??

Answer given below by Vikrant is correct .

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) => 5 ≤ 5, 4 < 6 and 1 < 2
and
(iv) (0, 153) => 0 < 3 and no need to examine further
selected by
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 ?
+1 vote

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 .

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.

@
145 ≠ 265

0≠153

Does it also violate asymmetric conditions ??

(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