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

Условие:

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

Решение:

Оценка:

Посмотрим на простые делители чисел:

2,3,5,7,11,13,17,19,23,29,...

Заметим, что каждое выписанное число имеет по крайней мере два простых делителя, т.к. оно составное. Если число имеет два двузначных простых делителя, то оно, очевидно, не может быть двузначным (минимальное такое число -- 121 = 11*11).

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

Пример:

16 = 2*2*2*2

27 = 3*3*3

25 = 5*5

49 = 7*7

Ответ: 4.