Solution to 6 a) Show, using the pigeonhole principle, that in any set of 5 integers, at … - Sikademy
Author Image

Archangel Macsika

6 a) Show, using the pigeonhole principle, that in any set of 5 integers, at least two have the same remainder when divided by 4. (b) Use the extended pigeonhole principle to show that there are at least 3 ways of choosing 2 different numbers from 2, 3, 4, 5, 6, 7, 8, 9 so that all choices have the same sum. 7 Decide for each of the following relations whether or not it is an equivalence relation. Give full reasons. If it is an equivalence relation, give the equivalence classes. (a) Leta,b∈Z. DefineaRbifandonlyif ab ∈Z (4) (b) Let a and b be integers. Define aRb if and only if 3|(a − b) (In other words R is the congruence modulo 3 relation

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

6.a)

There are four possible remainders when an integer is divided by 4: 0, 1, 2, or 3. Therefore, by the pigeonhole principle at least two of the five given remainders must be the same.


b)

Total number of ways of choosing 2 different numbers:

n=C^2_8=\frac{8!}{6!2!}=28 (pigeons)


We can choose 2 different numbers:

5=2+3 - 1 way

6=2+4 - 1 way

7=2+5=3+4 - 2


7.

a)

The relation is reflexive: a^2\isin Z ,

 symmetric: ba\isin Z ,

transitive: if ab\isin Z and bc\isin Z , then ac\isin Z .

So, this is equivalence relation.

Equivalence classes: integer numbers


b)

The relation is reflexive: 3|(a-a)=3|0

symmetric: 3|(b-a)

transitive: if 3|(a-b) and 3|(b-c) , then 3|(a-c)

So, this is equivalence relation.

Equivalence classes: integer numbers divisible by 3


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3004-qpid-1703