Question
1). Given any set of seven integers, must there be two that have the same remainder when divided by 6? Why?
2.) Given any set of seven integers, must there be two that have the same remainder when divided by 8? Why?
A. Yes. Let X be the set of seven integers and Y the set of all possible remainders obtained through division by 6, and consider the function R from X (the pigeons) to Y (the pigeonholes) defined by the rule: R(n) = n mod 6. Now X has 7 elements and Y has 6 elements. Hence by the pigeonhole principle, R is not one-to-one: R(n1) = R(n2) for some integers n1 and n2 with n1 not equal to n2. But this means that n1and n2 have the same remainder when divided by 6. B. Yes. Let X be the set of seven integers and Y the set of all possible remainders obtained through division by 8, and consider the function R from X (the pigeons) to Y (the pigeonholes) defined by the rule: R(n) = n mod 8. Now X has 7 elements and Y has 8 elements. Hence by the pigeonhole principle, R is not one-to-one: R(n1) = R(n2) for some integers n1 and n2 with n1 not equal to n2. But this means that n1and n2 have the same remainder when divided by 8. C. No. Consider this set {1, 2, 3, 4, 5, 6, 7}. This set has seven elements no two of which have the same remainder when divided by 6.
D. No. Consider this set {1, 2, 3, 4, 5, 6, 7}. This set has seven elements no two of which have the same remainder when divided by 8
Explanation / Answer
A and D
