GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
716 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 (20k points)   | 716 views
@Arjun Sir, What is the correct ans ??

Answer given below by Vikrant is correct .

4 Answers

+14 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.4k 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 ?
+3 votes

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.9k 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 (221 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 Aug 2017
  1. Bikram

    4902 Points

  2. ABKUNDAN

    4704 Points

  3. akash.dinkar12

    3480 Points

  4. rahul sharma 5

    3158 Points

  5. manu00x

    3012 Points

  6. makhdoom ghaya

    2480 Points

  7. just_bhavana

    2388 Points

  8. stblue

    2138 Points

  9. Tesla!

    2060 Points

  10. joshi_nitish

    1758 Points


25,014 questions
32,141 answers
74,825 comments
30,185 users