Решение задачи 444

Условие:

На доске записано несколько трехзначных чисел. Все они составные, однако, любые два взаимно просты. Какое наибольшее количество чисел может быть на доске?

Решение:

Оценка:

Пусть на доске N чисел, рассмотрим множество наименьших простых делителей этих чисел, назовем это множество А. По условию в множестве А все числа различны. Покажем, что в множества А нет чисел, больших 31.

Действительно, пусть в множестве А есть число, не меньшее 37 (это следующее простое число после 31). Это значит, что есть трехзначное число M, у которого наименьший простой делитель не меньше 37. Но так как M составное, то оно имеет вид M=p₁p₂n, где p₁ и p₂ простые (не обязательно различные), а n — натуральное. Значит само M не меньше 37⋅37=1369, так как p₁≥37, p₂≥37, то есть M не трехзначное, противоречие.

Отсюда следует, что в А максимум 11 чисел (простых от 2 до 31 как раз 11 штук). Значит N не больше 11.

Пример:

Приведем пример одиннадцати чисел: 2⁶, 3⁵, 5³, 7³,11², 13², 17², 19², 23², 29², 31².

Ответ: Одиннадцать.