По окружности красным карандашом записали 49 различных натуральных чисел, меньших 100. Между каждыми двумя соседними красными числами записали си-ним их наибольший общий делитель. Могло ли случиться, что все синие числа различны?
Copyright © 2024 SCHOLAR.TIPS - All rights reserved.
Answers & Comments
Verified answer
Не могло.Заметим, что для двух неравных натуральных чисел n < m наибольший общий делитель не превышает [m/2], где квадратные скобки означают округление вниз до ближайщего целого. Тогда среди всех чисел, меньших 100, наибольшие общие делители могут принимать значения от 1 до 49 — всего 49 вариантов. Так как синих чисел как раз 49, то каждое число от 1 до 49 написано по разу.
Простые числа 41, 43 и 47 должны быть написаны синим. Существует только один способ получить такие числа: надо написать рядом красные 41 и 82, 43 и 86, 47 и 94. Поскольку все остальные числа взаимно просты с 41, 43 и 47, то радом с красными 41, 43 и 47 будут написаны по синей единице, и синих единиц будет не меньше двух.