Question

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

Answer 1

Ответ:

123

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

если убрать все четные то получется 123, ответ првильный так как сумма двух нечет = четному, а нечет не делится на четное.

Answer 2

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

Обозначим стертые числа через \(a_1, a_2, \ldots, a_k\). После стирания этих чисел на доске останется множество чисел \(S = \{1, 2, 3, \ldots, 255\} \setminus \{a_1, a_2, \ldots, a_k\}\).

Теперь мы должны найти такие числа в множестве \(S\), чтобы никакое из оставшихся чисел не делилось на разность никаких двух других чисел. Рассмотрим возможные варианты:

1. Если в множестве \(S\) есть четное число, то оно не должно делиться на 2, так как иначе разность с другим четным числом будет четной, что нарушит условие. Таким образом, в \(S\) может остаться максимум одно четное число.

2. В \(S\) не может быть чисел вида \(2^p\), где \(p > 1\), так как разность двух степеней двойки всегда делится на 2.

3. Если в \(S\) есть простые числа, то никакие два из них не должны иметь общих делителей (кроме 1). В противном случае разность будет делиться на этот общий делитель.

Итак, для максимального количества чисел на доске мы выбираем:

- В множестве \(S\) остается одно четное число (если таковое было). - В множестве \(S\) остаются все простые числа, не имеющие общих делителей.

Таким образом, максимальное количество чисел на доске - это количество простых чисел, не имеющих общих делителей, плюс, возможно, одно четное число. Определим это количество:

Известно, что простых чисел от 1 до 255 всего 55 (включая 2 и 5, так как они не имеют общих делителей). Таким образом, максимальное количество чисел на доске - 55, а если есть хотя бы одно четное число, то максимальное количество - 56.

Таким образом, ответ: максимальное количество чисел, которые могли остаться на доске, равно 55 (если все оставшиеся числа нечетные) или 56 (если есть хотя бы одно четное число).