search
Log In
0 votes
357 views

How many ordered pair of integers (ab) are needed to guarantee that there are two ordered pairs (a1b1) and (a2b1) such that a1 mod 5 = a2 mod 5 and b1 mod 5 = b2 mod 5? should not answer be 25 here

in Graph Theory 357 views
0
It should be 26.

2 Answers

1 vote
 
Best answer

Based on pigeonhole principle.

You want minimum number of pairs (a,b) to ensure such that

(a1,b1) (a2,b2) pairs exist in a way

a1=a2mod5 and b1=b2mod5

In a pair(a,b)

a can belong to any of the residue of mod 5(0,1,2,3,4)-Total of 5 values.

Similarly b can take a total of 5 values.

Since a and b can be selected independently, a maximum of total 25(5x5) ordered pairs can be there which can sure that IN NO WAY two pair will exist such that,

(a1,b1) (a2,b2

a1=a2mod5 and b1=b2mod5

but now since, you have exhausted all the possibilities to make any new pair,now if you make one extra pair, it is guaranteed to have been repeated from the set of 25 ordered pairs formed above.

Hence, you need minimum 26 ordered pairs to ensure that

(a1,b1) (a2,b2) pairs exist in a way

a1=a2mod5 and b1=b2mod5


selected by
0 votes
consider this like-there are 5 holes each corresponding to remainders of 5 => 0,1,2,3,4

a1 and a2 will always occupy the same hole

b1 and b2 will always occupy the same hole

a1 and a2 have 5 choices(put them in any one hole). similarly, b1 and b2 have 5 choices(put them in any one hole)

total 5*5=25

$\left \lceil \frac{n}{25} \right \rceil=2$

n=26

Related questions

0 votes
2 answers
1
236 views
How to solve it(clear explanation please)
asked Jan 14, 2019 in Graph Theory Raja Rawal 236 views
0 votes
0 answers
2
81 views asked Nov 5, 2018 in Graph Theory Lone Wolf 81 views
0 votes
1 answer
3
158 views
What is the coefficient of x^(12) in the power series of
asked Feb 1, 2018 in Graph Theory Kaluti 158 views
0 votes
1 answer
4
151 views
Consider the following statements: S1: Every cyclic group is Abelian group. S2: Every Abelian group is cyclic group. S3: Cyclic group of order 10 have 4 generators. Which of the following is true?
asked Feb 1, 2018 in Graph Theory Kaluti 151 views
...