The Gateway to Computer Science Excellence

+42 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$

- $4$
- $6$
- $16$
- $24$

+36 votes

Best answer

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$

+56 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

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

+1

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

Thanks .

Thanks .

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

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

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

Hence, the answer is 16.

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

+12 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.

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.

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.

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

So any other value different from all those 15 combinations would do.

+3 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**.

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

0 votes

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.

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

0 votes

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

52,217 questions

59,926 answers

201,117 comments

118,162 users