The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2.1k views

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 Set Theory & Algebra by Veteran (18k points)
edited by | 2.1k views
anyone please explain the question clearly...

3 Answers

+25 votes
Best answer
order pair 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 ll surely match with one of the above 15 combination.(Pigeon Hole principle)
total 15+1 = 16 combination
answered by Veteran (53.7k points)
selected by
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 )$

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
+15 votes

Let's 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. There are 15 possibilities.

Now if we had 16 of these tuples, surly two of these will map to same combination. Hence answer 16.

 

answered by Active (1.9k points)
edited by
+6 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 (5.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.

@MiNiPanda

Good approach!!!

@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

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


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

33,687 questions
40,231 answers
114,272 comments
38,803 users