Problem 2135

Solution:
An integer is divisible by $6$, $7$ and $8$ if and only if it is divisible by their Least Common Multiple, which equals $6 \times 7 \times 4 = 168$.
Let $n$ be a positive integer and let $A$ be an arbitrary set of $n$ consecutive positive integers. Replace each number $a_{i}$ from $A$ with its remainder $r_{i}$ (mod $168$). The number $a_{i}$ is divisible by $6$ ($7$ or $8$) if and only if its remainder $r_{i}$ is divisible by $6$ (respectively $7$ or $8$). The difference $|a_{i} - a_{j}|$ is divisible by $168$ if and only if their remainders $r_{i} = r_{j}$.
Choosing $k$ numbers from the initial set $A$, which verify the required conditions, is the same as choosing $k$ of their remainders (mod $168$) such that:
1. each chosen remainder is not divisible by $6$, $7$ and $8$;
2. all chosen remainders are different.
Suppose we have chosen $k$ numbers from $A$, which verify the conditions. Therefore, all remainders are different and $k \leq 168$ (otherwise, there would be two equal remainders).
Denote by $B = \{0, 1, 2, 3, \ldots, 167\}$ the set of all possible remainders (mod $168$) and by $B_{m}$ the subset of all elements of $B$, which are divisible by $m$. Compute the number of elements of the following subsets:
$$\begin{gathered} |B_{6}| = 168 / 6 = 28, \quad |B_{7}| = 168 / 7 = 24, \quad |B_{8}| = 168 / 8 = 21 \\ |B_{6} \cap B_{7}| = |B_{42}| = 168 / 42 = 4, \quad |B_{6} \cap B_{8}| = |B_{24}| = 168 / 24 = 7 \\ |B_{7} \cap B_{8}| = |B_{56}| = 168 / 56 = 3, \quad |B_{6} \cap B_{7} \cap B_{8}| = |B_{168}| = 1 \end{gathered}$$
Denote by $D = B_{6} \cup B_{7} \cup B_{8}$, the subset of all elements of $B$, which are divisible by at least one of the numbers $6$, $7$ or $8$. By the Inclusion-Exclusion principle we get
$$\begin{gathered} |D| = |B_{6}| + |B_{7}| + |B_{8}| - (|B_{6} \cap B_{7}| + |B_{6} \cap B_{8}| + |B_{7} \cap B_{8}|) + |B_{6} \cap B_{7} \cap B_{8}| = \\ 28 + 24 + 21 - (4 + 7 + 3) + 1 = 60. \end{gathered}$$
Each chosen remainder belongs to the subset $B \setminus D$, since it is not divisible by $6$, $7$ and $8$. Hence, $k \leq |B \setminus D| = 168 - 60 = 108$.
Let us show that the greatest possible value is $k = 108$. Consider $n = 168$. Given any collection $A$ of $168$ consecutive positive integers, replace each number with its remainder (mod $168$). Choose from these remainders $108$ numbers, which constitute the set $B \setminus D$. Finally, take $108$ numbers from the initial set $A$, having exactly these remainders. These $k = 108$ numbers verify the required conditions.