Азиатско-Тихоокеанская математическая олимпиада, 2001 год

Найдите такое наибольшее натуральное число $N$, что количество целых чисел в наборе $\{1,2,\ldots ,N\}$, которые кратны 3 равно количеству чисел, кратных 5 или 7 (или кратных обоим одновременно).

Комментарий/решение

Заметим, что эта задача сводится к кому чтобы найти максимальное число удовлетворяющее $[\frac{N}{3}] + [\frac{N}{35}] = [\frac{N}{5}] + [\frac{N}{7}]$. Заметим, что $$\frac{N -2}{3} + \frac{N -34}{35} \leq [\frac{N}{3}] + [\frac{N}{35}] = [\frac{N}{5}] + [\frac{N}{7}] \leq \frac{N}{5} + \frac{N}{7}$$ Откуда $N \leq 86$. Если $N \geq 70$ то верно $$\frac{N -2}{3} + \frac{N - 16}{35} \leq [\frac{N}{3}] + [\frac{N}{35}] = [\frac{N}{5}] + [\frac{N}{7}] \leq \frac{N}{5} + \frac{N}{7}$$ Откуда $N \leq 59$, противоречие. Значит $N \leq 69$. Перебирая числа $69, 68, 67, 66, 65$ находим, что наибольшее такое число это $65$.