The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+33 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$
asked in Combinatory by Boss (16k points)
edited by | 3.8k views
anyone please explain the question clearly...

4 Answers

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

answered by Active (2k points)
edited ago by
+40 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
answered by Veteran (59.7k points)

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

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


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


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

answered by Boss (21.7k points)
(c,d) should be from above set?
c and d can be any non negative numbers. Not necessarily from the above set.
ok thanks.... installed correct procedure.


Good approach!!!



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

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

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.
0 votes
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.
answered by Loyal (6.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,084 answers
70,995 users