ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98591
Темы:    [ НОД и НОК. Взаимная простота ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

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


Ответ

Нельзя.

Замечания

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

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .