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:
(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: ,
symmetric: ,
transitive: if and , then .
So, this is equivalence relation.
Equivalence classes: integer numbers
b)
The relation is reflexive:
symmetric:
transitive: if and , then
So, this is equivalence relation.
Equivalence classes: integer numbers divisible by 3