GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
575 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)
asked in Set Theory & Algebra by Veteran (19.2k points)   | 575 views
@Arjun Sir, What is the correct ans ??

Answer given below by Vikrant is correct .

4 Answers

+13 votes
Best answer
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.3k points)  
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 .

answered by Loyal (4.7k points)  
0 votes

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 (211 points)  

@Aman_verma
145 ≠ 265

0≠153

Does it also violate asymmetric conditions ??

 

0 votes

(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 (365 points)  


Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1616 Points

  3. sh!va

    1580 Points

  4. Arjun

    1326 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1028 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    972 Points

  9. LeenSharma

    810 Points

  10. srestha

    662 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    242 Points

  2. Ahwan

    138 Points

  3. joshi_nitish

    112 Points

  4. jjayantamahata

    104 Points

  5. Aditya GN

    63 Points


22,725 questions
29,056 answers
65,052 comments
27,565 users