edited by
13,263 views
60 votes
60 votes

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 by

9 Answers

Best answer
56 votes
56 votes

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 by
78 votes
78 votes
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
17 votes
17 votes

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

5 votes
5 votes

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 by
Answer:

Related questions

36 votes
36 votes
6 answers
1
Kathleen asked Sep 22, 2014
24,490 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)...