Задача 65906

Темы:    [ НОД и НОК. Взаимная простота ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 8,9,10

Условие

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

Решение

  Оценка. Так как любые два записанных числа взаимно просты, то каждое из простых чисел 2, 3, 5 и 7 может войти в разложение на множители не более, чем одного из них. Если на доске пять или более чисел, то все простые множители в разложении какого-то из них должны быть не меньше чем 11. Но это составное число, значит, оно не меньше чем 121. Это противоречит условию. Следовательно, на доске записано не более четырёх чисел.
  Пример. 25, 26, 33, 49.

Ответ

4 числа.

Источники и прецеденты использования

олимпиада
Название	Окружная олимпиада (Москва)
год
Год	2016
класс
Класс	9
задача
Номер	9.2