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
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
Comments
Leave a comment