9.5. From the natural numbers from 1 to 1239, 384 different numbers were selected such that the difference between any two of them is not equal to 4, 5, or 9. Is the number $625$ selected?
Answer. Yes.

Solution.

Lemma. Among any 13 consecutive natural numbers, one can choose no more than four such that no two of them differ by 4, 5, or 9.

Proof of the lemma. Divide the 13 numbers $a, a+1, \ldots, a+12$ into 9 groups (of one or two numbers) and write the groups in a circle in the following order: $\{a+4\},\{a, a+9\}$, $\{a+5\},\{a+1, a+10\},\{a+6\},\{a+2, a+11\},\{a+7\},\{a+3, a+12\},\{a+8\}$. If 5 or more numbers are chosen, then some two of them will end up in the same group or in adjacent groups. However, from two adjacent groups, no more than one number can be chosen. The lemma is proved.

Now, let's mark the numbers $625, 626, 627, 628$, and divide all other numbers from 1 to 1239 into $(1239-4) / 13 = 95$ groups of 13 consecutive numbers (this is possible since 624 is divisible by 13). From the lemma, it follows that in groups of 13 numbers, no more than $95 \cdot 4 = 380$ numbers can be chosen in the required manner. Therefore, the four marked numbers $(625, 626, 627, 628)$ are chosen.

Note. Within each group of thirteen numbers, four numbers that satisfy the condition of the problem can be chosen. For example, before the number 625 in each group, take the numbers $a+4, a+5, a+6, a+7$, and after the number 628 in each group, take the numbers $a+5, a+6, a+7, a+8$. If this fact is not explained, no points are deducted, as the problem statement says that the described set of numbers exists.