Answer to Question #191580 in Discrete Mathematics for Leia

Question #191580

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


1
Expert's answer
2021-05-18T14:47:09-0400

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


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS