Question

На доске были написаны числа 1,2,3,…,235. Петя стёр несколько из них. Оказалось, что среди оставшихся чисел никакое не делится на разность никаких двух других. Какое наибольшее количество чисел могло остаться на доске? 50 баллов!!!!!

Answer 1

Ответ:

118

Пошаговое объяснение:

убрать все чётные числа

Answer 2

наверно 90. Я так думаю

Answer 3

Заметим, что если на доске есть числа $a$ и $b$ такие, что их разность $|a-b|$ встречается хотя бы дважды, то число $a-b$ будет являться делителем разности двух других чисел на доске. Следовательно, на доске не может быть двух чисел с одинаковой разностью.

Пусть на доске осталось $n$ чисел, тогда максимальное количество чисел, которые мы можем стереть, равно $235-n$. Нужно найти такое максимальное $n$, чтобы никакое из оставшихся чисел не было разностью двух других.

Рассмотрим случай, когда на доске оставлены числа не больше 15. Тогда мы можем записать все возможные разности между этими числами (их будет не более $\binom{15}{2}=105$). Из них нельзя выбрать две одинаковые, поэтому на доске не может быть больше $105+15=120$ чисел.

При этом можно показать, что существует набор из 120 чисел, удовлетворяющий условию задачи. Разобьем первые 235 чисел на 15 групп по 15 чисел в каждой и выберем среди них числа:
$$
15k+1, 15k+2, \dots, 15k+15,
$$
где $0 \le k \le 14$. В каждой группе эти числа образуют арифметическую прогрессию с разностью 1. Легко проверить, что никакие два числа из разных групп не имеют одинаковую разность.

Таким образом, на доске может остаться не более 120 чисел. С другой стороны, можно выбрать 120 чисел из первых 235, таких что никакое из них не является разностью двух других (например, можно выбрать все нечётные числа и все числа вида $4k+2$). Значит, ответ равен $\boxed{120}$.