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

Какое наибольшее количество двузначных чисел можно записать в ряд так, чтобы любые два соседних числа были не взаимно просты, а любые два несоседних числа — взаимно просты?

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. 10.
Решение. Десять чисел написать можно: 11, 77, 91, 65, 85, 51, 57, 38, 46, 23. Пусть нам удалось написать 11 таких чисел. Выпишем для каждой пары соседних чисел их общий делитель, отличный от 1. Получится 10 чисел, любые два из которых взаимно просты. Все эти числа либо однозначные, либо двузначные. Но нельзя выбрать более четырёх однозначных чисел, отличных от 1, любые два из которых взаимно просты. Поэтому в построенном ряду из 10 чисел будет не менее шести двузначных. Значит, какие-то два из них стоят рядом, и какое-то из чисел исходного ряда делится на каждое из них. Но, поскольку они взаимно просты, оно делится и на их произведение. А двузначное число не может делиться на произведение двух двузначных чисел.