Question

По окружности красным карандашом записали 49 различных натуральных чисел, меньших 100. Между каждыми двумя соседними красными числами записали си-ним их наибольший общий делитель. Могло ли случиться, что все синие числа различны?

Answer 1

Не могло.

Заметим, что для двух неравных натуральных чисел 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 будут написаны по синей единице, и синих единиц будет не меньше двух.

Answer 2

Да, все синие числа могли быть различными.

Поскольку мы записали 49 различных натуральных чисел меньше 100, то между каждыми двумя соседними красными числами мы записали их наибольший общий делитель. Наибольший общий делитель двух натуральных чисел всегда является натуральным числом. Таким образом, между каждыми двумя соседними красными числами мы записали натуральное число в качестве их наибольшего общего делителя.

Поэтому все синие числа могли быть различными, так как мы не имеем ограничений на то, какие именно натуральные числа мы могли записывать в качестве наибольшего общего делителя между красными числами.