Problem 8.5. The numbers $1, 2, 3, \ldots, 235$ were written on a board. Petya erased some of them. It turned out that among the remaining numbers, no number is divisible by the difference of any two others. What is the maximum number of numbers that could remain on the board?
Answer: 118.

Solution. 118 odd numbers could remain on the board: none of them is divisible by the difference of any two others, because this difference is even.

Suppose at least 119 numbers could remain. Consider 118 sets: 117 pairs $(1,2)$, $(3,4),(5,6), \ldots,(233,234)$ and one number 235. By the Pigeonhole Principle, in one of these sets, at least two numbers remained. This means that among the remaining numbers, there will be two consecutive numbers, but then their difference, equal to 1, is a divisor of any other remaining number. Contradiction.