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

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.