a) Verify that if we choose 3 or more integers from the set $\{6 k+1,6 k+2,6 k+3,6 k+4,6 k+5,6 k+6\}$, at least two will differ by 1, 4, or 5.

b) What is the largest number of positive integers less than or equal to 2022 that we can choose so that there are no two numbers whose difference is 1, 4, or 5?
Solution

a) Suppose, for the sake of contradiction, that we choose 3 or more integers and none of them differ by 1, 4, or 5. Since no difference is 1, we can assume that all differ by at least 2, and since no difference is 5, we cannot simultaneously choose $6k+1$ and $6k+6$. If $6k+1$ is not chosen, we must choose $6k+2, 6k+4, 6k+6$, and in this case, we have two that differ by 4. On the other hand, if $6k+1$ is chosen, we must choose $6k+1, 6k+3, 6k+5$, and thus we also have two numbers that differ by 4. This contradiction shows that it is not possible to choose 3 or more integers without having differences of 1, 4, and 5 between two of them.

b) Divide the 2022 integers into $\frac{2022}{6}=337$ disjoint sets of 6 consecutive numbers. From the previous item, if we choose more than 2 elements from one of these sets, we can find differences of 1, 4, or 5 among them. Therefore, the maximum number of elements that can be chosen is $337 \cdot 2 = 674$. To verify that this number is
realizable, it suffices to choose all the multiples of 3 from the list, which total $\frac{2022}{3}=674$. Since the difference between any two multiples of 3 is a multiple of 3, it follows that none of these differences can be 1, 4, or 5.