GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
458 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 (18.4k points)   | 458 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.2k 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.1k 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 ago by (191 points)  
Top Users Jan 2017
  1. Debashish Deka

    8968 Points

  2. sudsho

    5326 Points

  3. Habibkhan

    4798 Points

  4. Bikram

    4532 Points

  5. Vijay Thakur

    4486 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4196 Points

  8. santhoshdevulapally

    3808 Points

  9. Sushant Gokhale

    3596 Points

  10. Kapil

    3486 Points

Monthly Topper: Rs. 500 gift card

19,212 questions
24,104 answers
53,150 comments
20,319 users