
NT 3. Find the largest integer $k(k \geq 2)$, for which there exists an integer $n(n \geq k)$ such that from any collection of $n$ consecutive positive integers one can always choose $k$ numbers, which verify the following conditions:

1. each chosen number is not divisible by 6 , by 7 and by 8 ;
2. the positive difference of any two different chosen numbers is not divisible by at least one of the numbers 6,7 or 8 .


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 $\left|a_{i}-a_{j}\right|$ 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$ 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 ( $\bmod 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}
\left|B_{6}\right|=168: 6=28, \quad\left|B_{7}\right|=168: 7=24, \quad\left|B_{8}\right|=168: 8=21 \\
\left|B_{6} \cap B_{7}\right|=\left|B_{42}\right|=168: 42=4, \quad\left|B_{6} \cap B_{8}\right|=\left|B_{24}\right|=168: 24=7 \\
\left|B_{7} \cap B_{8}\right|=\left|B_{56}\right|=168: 56=3, \quad\left|B_{6} \cap B_{7} \cap B_{8}\right|=\left|B_{168}\right|=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 got

$$
\begin{gathered}
|D|=\left|B_{6}\right|+\left|B_{7}\right|+\left|B_{8}\right|-\left(\left|B_{6} \cap B_{7}\right|+\left|B_{6} \cap B_{8}\right|+\left|B_{7} \cap B_{8}\right|\right)+\left|B_{6} \cap B_{7} \cap B_{8}\right|= \\
28+24+21-(4+7+3)+1=60 .
\end{gathered}
$$

Each chosen remainder belongs to the subset $B \backslash D$, since it is not divisible by 6,7 and 8 . Hence, $k \leq|B \backslash 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 ( $\bmod 168$ ). Choose from these remainders 108 numbers, which constitute the set $B \backslash D$. Finally, take 108 numbers from the initial set $A$, having exactly these remainders. These $k=108$ numbers verify the required conditions.
