GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
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)
asked in Set Theory & Algebra by Veteran (19.1k points)   | 562 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.6k 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 (361 points)  


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arunav Khare

    1464 Points

  10. Arjun

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,062 answers
63,294 comments
24,160 users