Pigeonhole principle : Prove that if we take 46 numbers from sequence 0,1,2,..,80 then are 2 numbers that subtraction can divided by 9

Question

Prove that if we take 46 numbers from sequence 0,1,2,..,80 then are 2 numbers that subtraction can divided by 9

knowing that subtracting 2 numbers with same remainders of dividing by 9 the result is a number that divides by 9 without remainders

Answer 1

Start with a simpler proposition :

Choose any 4 distinct integers. Then the difference between at least 2 of those numbers will be a multiple of 3.

Proof : On division by 3 all integers have a remainder of either 0, 1 or 2.

Suppose our 1st choice has remainder 0. To avoid creating a difference which is a multiple of 3, our 2nd and 3rd choices must have different remainders 1 and 2. Now the 4th choice must repeat one of the previously-used remainders, because there are only 3 available : it is guaranteed to create a difference which is a multiple of 3.

This method can be used to prove that :

In any set of $n$ distinct integers there are at least 2 numbers which have a difference which is a multiple of $1, 2, 3, ... n-1$.

Answer 2

I think that Tony K's comment to the original query is the only way to make the problem non-trivial, and this answer presumes that Tony K's interpretation is accurate.

Let the residue of an integer $n$ denote the unique integer $r \,\in \,\{0,1,2, \cdots, 8\} \;\ni n \equiv r \pmod{9}.$

Since there are 9 equivalence classes (re the residue of a number), and since 46 numbers from $\{0,1, \cdots, 80\}$ are selected, the pigeonhole principle implies that at least one of the 9 equivalence classes has had $6$ numbers taken from it.

WLOG, assume that it is the equivalence class corresponding to $n \equiv 0 \pmod{9}.$

Consider the subset $\{0, 18, 36, 54, 72\}.$ When you add one more different number $m$ to that subset, where $m \equiv 0 \pmod{9},$ and $0 \leq m \leq 80,$ then there must be two numbers in that subset that differ by exactly 9.

Answer 3

If we take this problem be:

If we choose 46 numbers from $\{1,\cdots, 80\}$ prove that there will be a pair whose difference equals 9.

This problem is a bit more interesting.

Lets look at a simpler example, first.

Suppose we have 18 numbers in the set. If we choose 10, there must be a pair that have a a difference of 9.

Pair-off numbers the numbers in $\{1,\cdots, 9\}$ with corresponding numbers in $\{10,\cdots, 18\}$

The set $\{1,\cdots, 9\}$ represents all of our pigeon-holes. If we have 10 numbers we will have guaranteed to fill all of our pigeon holes, and have one pigeon hole with two pigeons.

Expanding our problem to have 80 pigeons, we additionally pair-off

The subsets $\{19,\cdots, 27\}, \{28,\cdots, 36\}$ and $\{37,\cdots, 45\}, \{46,\cdots, 54\}$ and $\{55,\cdots, 63\}, \{64,\cdots, 72\}$ as well.

This removes 36 members from the original set, leaving 44 pigeon holes. With 45 pigeons there must be one pigeon-hole with more than one pigeon.