Question

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

Answer 1

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