Question

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

Answer 1

Ответ:

Наверное 264 но это не точно

Объяснение:

Answer 2

Давайте рассмотрим, какие числа Петя мог стереть так, чтобы среди оставшихся не было чисел, делящихся друг на друга.

Итак, если на доске остались только простые числа, то у нас не будет проблем с их делимостью. Однако, чтобы максимизировать количество оставшихся чисел, давайте посмотрим, какие составные числа Петя мог стереть.

Допустим, Петя стер числа, кратные 2. В этом случае останутся все нечетные числа от 1 до 265 включительно. Известно, что любое четное число можно представить в виде произведения простых чисел. Например, 6 = 2 * 3. Таким образом, если мы уберем все кратные 2, останутся только числа, не делящиеся друг на друга.

Теперь рассмотрим числа, кратные 3. Если мы уберем все кратные 3, останутся числа, не делящиеся друг на друга.

Продолжим этот процесс для всех простых чисел, меньших или равных квадратному корню из 265 (поскольку, если есть пара чисел, произведение которых равно 265, то одно из них должно быть меньше или равно квадратному корню из 265).

Таким образом, у нас останутся все простые числа от 1 до 265 включительно, а также числа, которые не имеют простых делителей в этом диапазоне. Максимальное количество таких чисел можно найти, вычитая из общего числа (265) количество простых чисел до квадратного корня из 265.

Квадратный корень из 265 округленный вниз ближайшим целым числом - это 16. Таким образом, у нас есть 16 простых чисел от 1 до 16 включительно. Поэтому максимальное количество чисел, которые могли остаться на доске, равно 265 - 16 = 249.