# GATE2005-44

5.6k views

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs $(a,b)$ and $(c,d)$ in the chosen set such that,  $a \equiv c\mod 3$   and   $b \equiv d \mod 5$

1. $4$
2. $6$
3. $16$
4. $24$

edited
2
anyone please explain the question clearly...

Let us pick any tuple $(p, q)$ from $\mathbb{N}^2$

What can happen?

Well, $p\mod 3$ can be $0,1$ or $2.$ And $q \mod 5$ can be $0, 1, 2, 3$ or $4.$ So, there are $15$ possibilities.

Now if we have $16$ of these tuples, surely two of these will map to same combination. Hence, answer is $16.$

Correct Answer: $C$

edited
Order pairs for $(a,b)$ are
$(0,0), (0,1), (0,2), (0,3), (0,4)\\ (1,0), (1,1), (1,2), (1,3), (1,4)\\ (2,0), (2,1), (2,2), (2,3), (2,4)$
Take any other combination for $(c,d)$ that will surely match with one of the above $15$ combinations (Pigeon Hole principle)
Total $15+1 = 16$ combinations
0
yes

(a,b)=15 combination

(c,d)=1 combination
1
Hi , can you please explain the condition (a=c mod 3) and (b=d mod 5) and how it is satisfied .

Thanks .
0

0
3
Please explain the answer in a quick and logical way. We cannot use brute force methods to solve problems as there as it is a time bounded exam.
4
Actually meaning here is important

$a\equiv b\left ( mod m \right )$

means there is an integer k such that $a-b=km$

Now check any pair like$\left ( 1,3 \right )$ and $\left ( 2,4\right )$
6
14

What is the minimum number of ..?

Usually questions which states "minimum number of" or phrases like "atleast" they usually in most cases give us a hint that we should try out pigeonhole principle.

Okay, so we want minimum ordered pair of integers such that

for any pair (a,b) and (c,d)

a≡cmod3       and           b≡dmod5

holds.

mod 3 has 0,1,2 as residues or congruence classes.

mod 5 as 0,1,2,3,4 as residues or congruence classes,

Now a can be congruent to any of 0 or 1 or 2 (3 choices)

And b can be congruent to any of 0 or 1 or 2 or 3 or 4 (5 choice)

a can be chosen independently of b and vice versa

so total ways of ordered pair such formed = 3*5=15.

Now if, you take any two ordered pairs from these 15 pairs say (a,b) and (c,d)

It will always be the case that a!=c and b!=d or a=c but b!=d or a!=c but b=d in which case our condition

a ≡ c mod3  and     b ≡ d mod5 will violate.

Now if you seem to add one more ordered pair to these 15 pairs(16 or more ordered pairs)

then by pigeon hole principle it will be the case that

a=c and b=d for atleast 2 ordered pairs (a,b) and (c,d) will hold.

in which case our condition

a≡cmod3 and b≡dmod5

will get satisfied.

0
@Ayush i get how you are calculating 15  but please explain me bit more about how you add 1 more for this
3

@Brij Mohan-

Simple analogy- You have a set of 15 distinct objects, and they all are kept in bag.

You try 15 times, taking one object out and then putting back in.

In, all of those 15 times, it might be the case you every time picked up a different object (say as in you knew where exactly each of type of object in the bag was)

But when you go for the 16th trial, you would have definitely picked up among one of those 15 objects only.

So, here 15 distinct ordered pairs can be formed

by which

a≡cmod3a≡cmod3   and   b≡dmod5

I can violate with above condition, by playing with "and" because and wants both of them to be true.

But when I say exceed the quantity 15, surely some ordered pair will be repeated, for which

a≡cmod3a≡cmod3   and   b≡dmod5 condition will go true.

Minimum value to for exceeding? 15+1(just move a step ahead) =16

0

@Ayush Upadhyaya is this what you want to say:-

We need all entries, which are mentioned in the table and we require one more pair such that

$\text{(a,b)} : \forall a,b \in Z^+$

So, that all positive integer a,b satisfy the given condition:- a mod 3 = c and b mode 5 = d, and (c,d) are those pairs which are already present in our table.

For example, take any value of a and b, let (45, 13) for which (c,d) will be (0,1) which is already present in our table.

So, we just require one more pair (a,b), In total, we have 15 + 1 = 16.

0
someone plzz explain clearly so that others can undestand...i am not able to understand answers wen explained in standard way..give friendly answers..plzz
6

I hope u got the question meaning first. Now the task is, we have to find the minimum number of ordered pairs of non-negative numbers which means ordered pairs start from (0,0) to till the last nonnegative number, suppose it is (N, N).

They are giving two expressions which say a ≡ c mod  3 which means a and c will leave the same remainder when we divide them with 3.

Ex: 24 ≡ 12 mod 3, 15 ≡ 18 mod 3

Similarly, another expression has also a similar meaning.

whenever we divide any number with 3, there are 3 possibilities of remainders:(0,1,2) and when we divide the number with 5, there are possibilities of remainders:(0,1,2,3,4).

So we have total 3 *5 = 15 pairs which starts from (0,0),(0,1) .........(2,4)

Now it is becoming like a function in the sense we will give any pair of input( from (0,0) to (N, N)) then we will check it maps to which possibilities among((0,0),(0,1)..............(2,4)).

we can also take this way, there are 15 boxes ; (0,0) - Box 1, (0,1) - Box 2 ,.......(2,4) -Box 15

Now when we take any non-negative ordered pair, we put (0,0) to Box 1, (0,1) to Box 2 ,.....(2,4) to Box 15,

next, when we take any ordered pair now if it is satisfying conditions of expressions, it will sit in one of the 15 Boxes, we have found out, we have to take a minimum of 16 ordered pairs, we can treat these ordered pairs as Pigeons, there will at least 16 Pigeons (ordered pairs).

0
Now got it !!

(a≡c mod 3) means remainder values 'a' can get when 'c' is divided by 3. It is {0,1,2}.

(b≡d mod 5) remainder values 'b' can get when 'd' is divided by 5. It is {0,1,2,3,4}.

Whatever be the values of c and d, we can at most get 15 combinations of a and b.( i,e (0,0) (0,1) (0,2) (0,3) (0,4) ......(2,0) (2,1) (2,2) (2,3) (2,4) total 5*3=15.

As here we need to find the minimum number of ordered pairs, so taking any value for (c,d) will do. Therefore we consider 1 for (c,d).

Total number of ordered pairs become 15+1=16.

0
(c,d) should be from above set?
2
c and d can be any non negative numbers. Not necessarily from the above set.
0
ok thanks.... installed correct procedure.
0

@MiNiPanda

Good approach!!!

0

@mini

how (c,d) value not necessary from the set ?

what if (a,b) (c,d) is (0,0)(4,6)

here neither

(a≡c mod 3) nor

(b≡d mod 5)  is satisfied

1
@A_i_$_h we calculate the values of a and b from c and d respectively. We can't map any (c,d) pair to any (a,b) pair. 1st we need to know the values of (c,d) and then get (a,b) out of it which is sure to get matched with one of those 15 combinations. In your example, if I am not wrong, you are asking (4,6) to get mapped to (0,0) which is not possible. It will get mapped to (1,1) only. 0 @minipanda okay :) i got that 15 combination concept but why 1 is added is still not very clear 5 @A_i_$_h Suppose we don't consider that 16th pair and all we have is that set of 15 combinations. So choose any pair for (c,d) let it be (1,4) and what you get after applying those modulo functions is same as (1,4). Similarly for any pair you choose, it gets mapped to that pair itself. But in the question it has been asked to ensure that there are "two" distinct pairs (a,b) and (c,d) such that ....

So any other value different from all those 15 combinations would do.
0
There is nothing like distinct written in question? then how can we say (a,b) & (c,d) are distinct pairs?

Let $\mathbb{Z^{+}}=\mathbb{N}\cup\{0\}=\{0,1,2,3,4,5,...\}$

\begin{align}\therefore \mathbb{Z^{+}}\times \mathbb{Z^{+}}=\{&(0,0),(0,1),(0,2),...,\\&(1,0),(1,1),(1,2),...,\\&(2,0),(2,1),(2,2),...,\\&.....................,\\&(100,0),(100,1),(100,2),(100,3),...,\\&.....................\}\end{align}

To answer this question, we need to think of the worst case. How many pairs are there at least to take from $\mathbb{Z^{+}}\times \mathbb{Z^{+}}$ where for any two pairs $(a,b),(c,d)$ the condition $a \equiv c \mod 3$ and $b \equiv d \mod 5$ doesn't hold?

The answer is $3\times5=15$.

Proof: For any integer $x \mathrm{~mod~}3$ has the residues from the set $\{0,1,2\}=A$ [Let]. Likewise for $x \mathrm{~mod~} 5$ has the residues from the set $\{0,1,2,3,4\}=B$ [Let].

Now,

\begin{align} A \times B=\{&(0,0),(0,1),(0,2),(0,3),(0,4),\\&(1,0),(1,1),(1,2),(1,3),(1,4),\\&(2,0),(2,1),(2,2),(2,3),(2,4)\}\end{align}
This set of ordered pairs doesn't hold the condition because there are no two pairs $(a,b),(c,d)$ such that $a \equiv c \mod 3$ and $b \equiv d \mod 5$.

Here, $|A \times B|=|A|\times|B|=3 \times 5=15$.

So for the worst case, we have to take at least $15$ pairs from $\mathbb{Z^{+}}\times \mathbb{Z^{+}}$. Now taking any other pair (only one more) will hold the required condition. Because for any other pair $(x,y)$, we have $(x\mod 3, y\mod5)$ will produce any pair from $A \times B$. [For example, take $(95,101)$, then we can have $(95\mod3,101\mod5)\equiv(2,1)\in A \times B$].

Therefore, we have to take $15+1=16$ pairs from $\mathbb{Z^{+}}\times \mathbb{Z^{+}}$.

So the correct answer is C.

edited
1 vote
Using extended pigeonhole principle, we have 15 different buckets(mod 3 * mood 5). Now we want value of N such that ceil (N/k)=2. Smallest value satisfying this N is 16 and hence the answer.
1 vote

$Mod\ 3\rightarrow remainders: 0,1,2$

$Mod\ 5\rightarrow remainders: 0,1,2,3,4$

$Total\ pairs\rightarrow 5\times 3=15$

$(0,0),(0,1),(0,2)...,(2,0),(2,1)...,(2,4)$

Now pick any two pairs $(a,b)\&(c,d)$ and try to satify $a\equiv cmod3\ \&\ b\equiv dmod5.$

None of these pairs will satify this condition, that's why we will go out and find a new pair that can satify our need.

Question asked for minimum and hence we will welcome only a single pair into our team of already 15 pairs.

$\therefore 15+1=16\ pairs\ in\ total$

I know it's really late to add this doubt, and it might seem pretty silly, but the question asks "the minimum number of ordered pairs, such that  a≡cmod3   and   b≡dmod5"

Shouldn't the answer be, uhm, 2?

I choose a set, S = { (6,15), (3,10) }. It satisfies the condition.
0

Here, the minimum number of ordered pairs $(a,b),(c,d)$ means that it guarantees $100\%$ (always) satisfying the condition.

If you take just two pairs only, that doesn't guarantee that those pairs will satisfy the condition always. Even if you take three pairs, they won't satisfy the condition always either. This thing is true up to $15$ random pairs. After that just take one more pair, the condition must be satisfied always. That's why the answer is $16$.

1
Well, that was an old post, haha. I understand it now. Thank you, though :)
0
It's okay. :)
Keep solving. 👍

Let N be the minimum no of ordered pairs required.

p mod 3 can be 0,1 or 2. And q mod 5 can be 0,1,2,3 or 4. So, there are 15 possibilities. i.e holes =15.

By Generalized pigeon hole,

$\left \lceil \frac{N}{holes} \right \rceil$ = 2 (since there are 2 pairs (a,b) and (c,d) )

$\left \lceil \frac{N}{15} \right \rceil$ = 2

The minimum integer value of N satisfying above equation is 16 (as $\left \lceil \frac{16}{15} \right \rceil$ = 2)

Hence option C is correct.

## Related questions

1
8.1k views
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be: $O(n)$ $O(n \log n)$ $O \left( n^{\frac{3}{2}} \right)$ $O\left(n^3\right)$
Consider the set $H$ of all $3 * 3$ matrices of the type $\left( \begin{array}{ccc} a & f & e \\ 0 & b & d \\ 0 & 0 & c \end{array} \right)$ where $a,b,c,d,e$ and $f$ are real numbers and $abc ≠ 0.$ Under the matrix multiplication operation, the set $H$ is: a group a monoid but not a group a semi group but not a monoid neither a group nor a semi group
Let $f: B \to C$ and $g: A \to B$ be two functions and let $h = f o g$. Given that $h$ is an onto function which one of the following is TRUE? $f$ and $g$ should both be onto functions $f$ should be onto but $g$ need not to be onto $g$ should be onto but $f$ need not be onto both $f$ and $g$ need not be onto
Let $R$ and $S$ be any two equivalence relations on a non-empty set $A$. Which one of the following statements is TRUE? $R$ $∪$ $S$, $R$ $∩$ $S$ are both equivalence relations $R$ $∪$ $S$ is an equivalence relation $R$ $∩$ $S$ is an equivalence relation Neither $R$ $∪$ $S$ nor $R$ $∩$ $S$ are equivalence relations