Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, II тур дистанционного этапа

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

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ: нет, не могло.
Решение. Заметим, что НОД двух различных чисел, меньших 100, должен быть меньше 50, так как хотя бы одно из этих двух чисел больше НОД по крайней мере вдвое. Поэтому если все синие числа различны, то среди них есть все числа от 1 до 49. В частности, среди них есть простое число 47. Оно может получиться только как НОД красных чисел 47 и 94. Тогда второе синее число, соседнее с красным числом 47, равно 1. Аналогично показывается, что среди красных чисел есть простые числа 41 и 43, и рядом с каждым из них также должна стоять синяя единица. Но тогда синих единиц должно быть по крайней мере две, так как одно синее число соседствует только с двумя красными. Противоречие.