841 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 .

The question says that the partial ordern P is defined on the set of natural numbers. In option D, why (0,153) will be considered then (as 0 is not a natural number)?

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
answered by Veteran (13.7k points) 59 156 223
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 ?

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 .

answered by Boss (5.6k points) 3 9 32

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.

answered by (221 points) 3 3 8

@
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

answered by Junior (637 points) 1 4 9

1
2