Register

GATE IT 2007 | Question: 23

• edited by
18,981 views
53 53 votes

A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division.

  1. $(0, 0) \in P.$
  2. $(a, b) \in P$ if and only if $(a \% 10) \leq (b \% 10$) and $(\frac{a}{10},\frac{b}{10})\in  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)

9 Answers

Best answer
54 54 votes

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) \to 5 ≤ 5, 4 < 6$ and $1 < 2$
  • (iv) $(0, 153) \to 0 < 3$ and no need to examine further
• selected by
15 15 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 .
• edited by
14 14 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    

4 4 votes

In this problem.

a % b means the mod function (i.e residue when a is divided by b).

a/b means integer division (i.e quotient when a is divided by b)

i)   (101,22):

101% 10 ≤    22% 10

1≤ 2 which is true.

(101/10, 22/10)

(10, 2)∊  P need to check is  (10, 2) ∊ P

10% 10 ≤ 2% 10  

0 ≤2 which is True.

Then (10/10, 2/10)= (1, 0) fails since . (101, 22) not belongs to  P

(ii) (22, 101)

22% 10 ≤ 101% 10

2 ≤ 1 is False.

 (22, 101) not belongs to P

(iii) (145, 265)

145% 10 ≤ 265 % 10

5 ≤ 5 is true and (145/10, 265/10) = (14, 26) ∊ P has to be checked. Now consider (14, 26).

14% 10 ≤ 26% 10

4 ≤ 6 is true and (14/ 10, 26/10)= (1, 2) ∊ P has to be checked. Now consider (1, 2) 1% 10 ≤ 2% 10 15 2 is true and (1/10, 2/10)=(0, 0) ∊ P which is given to be true. Therefore (145, 265) ∊ P

(iv) (0, 153):

0% 10 ≤ 153% 10⇒  0 ≤ 3 is true

Then (0/10, 153/10)= (0, 15) should be in P (0,15):

0% 10 ≤ 15% 100 ≤ 5 is true.

Then (0/10, 15/10)= (0, 1) should be in P

(0, 1): 0% 10 ≤ 1% 100 ≤ 1 is true.

Then (0/10, 1/10)= (0, 0) should be in P It is given that (0, 0) ∊ P

Therefore (0, 153) ∊ P So (ii) and (iv) are contained in P

2 2 votes

Given that $(0,0)$ $\epsilon$ $P$.

And a pair $(a,b)$ will be in $P$ if $amod10$ is less than or equal to $bmod10$ and if $(a/10, b/10)$ is in $P$

Here $\leq$ is the mathematical operator and not the symbol that denotes a relation in POSET.

$(101,22)$

1 $\leq$ 2 True. And does  $(10,2)$ $\epsilon$ $P$?

0 $\leq$ 2. True. And does $(1,0)$ $\epsilon$ $P$?

1 $\leq$ 0. False.

So $(i)$ does not belong to P.

 

Options A and C eliminated.

If $(ii)$ is True then B is the answer. If not, then D is the answer. So check $(ii)$

$(22,101)$

2 $\leq$ 1. False.

So Option D

1 1 vote

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.

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2007 | Quest...Next → · GATE IT 2007 | Quest...
← Previous in category · GATE IT 2007 | Quest...Next in category → · GATE IT 2006 | Quest...
Position:
Show:

Related questions

29 29 votes
6 answers 6 answers
11.7k
11.7k views
Ishrat Jahan asked Oct 29, 2014
11,670 views
GATE IT 2007 | Question: 16
The minimum positive integer $p$ such that $3^{p} \pmod {17} = 1$ is$5$$8$$12$$16$
59 59 votes
3 answers 3 answers
20.3k
20.3k views
Kathleen asked Sep 21, 2014
20,340 views
GATE CSE 2007 | Question: 26
Consider the set $S =\{ a , b , c , d\}.$ Consider the following $4$ partitions $π_1,π_2,π_3,π_4$ on$S : π_1 =\{\overline{abcd}\},\quad π_2 =\{\overline{ab}, \overline{cd...
61 61 votes
5 answers 5 answers
35.5k
35.5k views
Ishrat Jahan asked Oct 30, 2014
35,499 views
GATE IT 2007 | Question: 85
Consider the $B^{+}$ tree in the adjoining figure, where each node has at most two keys and three links.Keys $K15$ and then $K25$ are inserted into this tree in that orde...
67 67 votes
5 answers 5 answers
25.6k
25.6k views
Ishrat Jahan asked Oct 30, 2014
25,637 views
GATE IT 2007 | Question: 84
Consider the $B^+$ tree in the adjoining figure, where each node has at most two keys and three links.Keys $K15$ and then $K25$ are inserted into this tree in that order....