Question

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

Answer 1

Ответ:

90

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

Долго писать

Answer 2

Для решения этой задачи можно использовать метод математической индукции.

Пусть у нас осталось n чисел на доске. Рассмотрим два случая:

1) Если на доске осталось только одно число, то очевидно, что оно не делится на разность никаких двух других чисел.

2) Предположим, что при n=k числах на доске никакое из них не делится на разность никаких двух других чисел.

Проверим, что при n=k+1 это условие также выполняется.

Рассмотрим два случая:

- Если удаляемое число не делится ни на одно из оставшихся чисел, то оно не влияет на выполнение условия задачи. То есть, если при n=k числах условие выполняется, то оно будет выполняться и при n=k+1.

- Если удаляемое число делится на разность двух других чисел, то оно делится и на их сумму. Пусть это числа a и b. Тогда, у нас на доске есть числа a, b и (a+b), и никакое из них не делится на разность никаких двух других чисел. Удалим числа a и b. Теперь на доске осталось (k-1) чисел, и по предположению индукции, никакое из них не делится на разность никаких двух других чисел. Таким образом, при n=k+1 условие задачи также выполняется.

Итак, мы показали, что при любом n условие задачи выполняется.

Так как изначально на доске было 265 чисел, то наибольшее количество чисел, которое могло остаться, равно 265.