Find largest subset in which all differences are divisible by $8$

Question

Define $S$ as a set of $99$ natural numbers, i.e., $S\subset N$ and $|S| = 99$. Note that the maximum occurrence of an element in a set should be $1$, that is to say, elements are not allowed to be repeated.

Assume the elements in $S$ are unknown to us. We want to find a set $P \subset S$ such that $$\forall x,y \in P,\quad |x−y| ≡ 0\!\!\!\!\mod 8\quad \text{(the difference of $x$ and $y$ is divisible by 8)}$$What is the maximum possible size of $P$ for any set $S$ (note that the size of $S$ must be exactly $99$ while the elements can be any natural numbers)? That is to say, what is the value of $$\min S\subset N,|S|=99 \max P \subset S |P |\text{?}$$

Answer 1

To guarantee $∀x,y ∈ P, |x−y| ≡ 0 \pmod 8$ for any arbitrary $S$, the largest such set can have $\left\lfloor\frac {99}8\right\rfloor+1=13$ elements since there are eight possible conjugacy classes and each conjugacy class will satisfy the required property.

Here's an example of a $(13\times 8=)104$ element $\tilde S$ where there is no such set with $14$ elements- \begin{align*} \{&8,16,24,\dots ,104\\ &9, 17, 25,\dots ,105\\ &10, 18, 26,\dots ,106\\ &.\\ &.\\ &.\\ &15, 23, 31,\dots ,113\} \end{align*} Any $99$ element subset $S\subset \tilde S$ does the job.

The proof is that any $x,y : |x−y| ≡ 0 \pmod 8$ must lie in the same line in the given diagram, and there are only $13$ elements in each line.

Answer 2

Suppose the elements of $S$ all have the same remainder modulo 8. In that case, the difference between any pairs of elements of $S$ is divisible by 8.

If $S$ is an arbitrary (finite) subset of $\mathbb{N}$, and you want to find the largest subset for which the difference between all elements is divisible by $8$: partition $S$ into the eight conjugacy classes modulo 8. The largest subset is then the largest conjugacy class.

Answer 3

If $P$ is such that $x-y$ is divisible by $8$ then $x\equiv y \pmod 8$ for any two elements or in other words, all $x\in P$ must have the same remainder, call it $r$ when divided by $8$. There are only $8$ such possible remainders. There are $99$ element so on average there are $\frac {99}8 = 12\frac 38$ elements for each possible remainder. As it is impossible for all remainders to have fewer than average number elements, there must be at least one remainder with greater than average, or $13$ elements with that number of elements.

So the answer it thirteen.