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

2 votes
2 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.
2 votes
2 votes

Let N be the minimum no of ordered pairs required.

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. i.e holes =15.

By Generalized pigeon hole,

$\left \lceil \frac{N}{holes} \right \rceil$ = 2 (since there are 2 pairs (a,b) and (c,d) )

$\left \lceil \frac{N}{15} \right \rceil$ = 2

The minimum integer value of N satisfying above equation is 16 (as $\left \lceil \frac{16}{15} \right \rceil$ = 2)

Hence option C is correct.

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

0 votes
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.
Answer:

Related questions

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