GATE CSE 2005 | Question: 44

Question

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$

• A. $4$
• B. $6$
• C. $16$
• D. $24$

Comments

anyone please explain the question clearly...

---

the answer is easy to get and not a challenging one however i think the way they have quoted the question is bad and making it unnecessarily hard, am i the only one who thinks so ?

Answer 1

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$

Comments

I’m literally breaking out my head to understand the question and answers provided here.

Just what I’m thinking is

Take set = {(3,4),(0,4)}

These two ordered pairs satisfy, a mod 3 = c and b mod 5 = d.

Why can’t just take such a set having a cardinality of 2 and take any superset that satisfies the given condition?

If say we should not be specific about the ordered pairs in the set and take a random set having 16 elements

S = {(4,5),(5,6),(6,7),(7,8),(8,9),(9,10),(11,12),(12,13),(13,14),(14,15),(15,16),(16,17),(17,18),(18,19),(19,20),(20,21)}

But there is no pair (a,b) and (c,d) that satisfies, a mod 3 = c and b mod 5 = d.

I’m sure I’m wrong.

But where am I getting things in the wrong way?

---

@mani312

a ≡ c mod3  means a mod 3 = c mod 3

b ≡ d mod5 means b mod 5 = d mod 5

Here (4,5)  and (19,20) satisfies above conditions.

 

---

Thanks @Arpit I've misinterpreted the congruence mod n definition.

Answer 2

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

Comments

yes

(a,b)=15 combination

(c,d)=1 combination

---

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

Thanks .

---

@iaser, can you explain your answer?

---

Please explain your answer with more details.

---

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.

---

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 )$

---

https://math.stackexchange.com/questions/1536906/what-is-the-minimum-number-of-ordered-pairs

This might help

---

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.

Hence, the answer is 16.

---

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

---

@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

---

@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.

---

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

---

 sunita24 

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).

---

Now got it !!

---

best explanation using Pigeonhole principle..Thank you @Ayush !

---

bro I got answer using combination
I am not getting answer using pigeonhole
I just want to understand how pigeonhole work in this question bro

Answer 3

(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.

Comments

@minipanda

okay :) i got that 15 combination concept but why 1 is added is still not very clear

---

@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.

---

There is nothing like distinct written in question? then how can we say (a,b) & (c,d) are distinct pairs?

Answer 4

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.