Given any set S of 6 natural numbers, must there be two numbers in S that have the same remainder when divided by 8?

Question

Answer the following questions and justify your answer. Hint: Use the (generalised) pigeonhole principle.

Given any set S of 6 natural numbers, must there be two numbers in S that have the same remainder when divided by 8?

My instinctive answer would be.... no? Since obviously, 'any' set of natural numbers could simply be 6 positive integers that do not have the same remainder when divided by 8. Of course, this being discrete math and not simple logic, I have to proof it. So I suppose my question is how to apply the generalised pigeonhole princip to disprove that for S, {n, m} have the same remainder when divided by 8.

-Apologies in advance, as I can see the pigeonhole princip has been featured before. I just cant seem to make anything of it.

Answer 1

Something is odd, on the face of it, about the "hint".

Here's a set of six natural numbers: $\{1,2,3,4,5,6\}$ with different remainders when divided -- zero times! -- by 8.

So we have an immediate boring proof by counterexample that it is false that, given any set $S$ of six natural numbers, there must be two numbers in $S$ that have the same remainder when divided by 8. The pigeonhole principle doesn't come into it!

(Was there a series of examples, perhaps, and you were supposed to spot which ones the pigeonhole principle is useful for??)

Answer 2

The key word here is questions. Plural.

As you revealed in a comment, what you copied was part of a set of three questions. You need the Pigeonhole Principle for the questions in parts (b) and (c) of the problem. You don't need it for part (a) (the question about a set of six numbers), which has a simple counterexample.