Задача 98591

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

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

Условие

Автор: Шаповалов А.В.

Все виды растений России были занумерованы подряд числами от 2 до 20000 (числа идут без пропусков и повторений). Для каждой пары видов растений запомнили наибольший общий делитель их номеров, а сами номера были забыты (в результате сбоя компьютера). Можно ли для каждого вида растений восстановить его номер?

Решение

Растения с номерами 101 и  10201 = 101²  (как и с номерами  8192 = 2¹³  и  16384 = 2¹⁴)  различить нельзя. Они имеют одинаковые наибольшие общие делители с любым числом, не превосходящим 20000. Поэтому воcстановить их номера не удастся.

Ответ

Нельзя.

Замечания

1. Годятся также любые два различных простых числа в пределах от 10001 до 20000.

2. Баллы: 8-9 кл. – 5, 10-11 кл. – 4.

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

олимпиада
Название	Турнир городов
Турнир
Дата	2002/2003
Номер	24
вариант
Вариант	осенний тур, основной вариант, 10-11 класс
Задача
Номер	1
олимпиада
Название	Турнир городов
Турнир
Дата	2002/2003
Номер	24
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
Задача
Номер	2