Question

из 104 натуральных чисел 1,2,3,4...104 требуется выбрать несколько чисел и расположить их по кругу так, чтобы произведение любых 2 соседних чисел делилось на 40. Какое наибольшее количество чисел можно выбрать?

Answer 1

Для того чтобы произведение двух чисел делилось на 40 необходимо чтобы среди множителей была хотя бы одна 5ка...
Всего чисел содержащих 5ку от 1 до 104 - 20чисел. 
Одной 5ки конечно мало, произведение также должно делиться и на восемь.
Среди тех 20ти чисел 3 из них делится на 4(для них возьмем соседние числа делящиеся на 2), 2 на 8, 5 на 2(для них возьмем соседние числа делящиеся на 4)...Оставшиеся 10 нечетны, для них возьмем соседние числа делящиеся на 8. Нетрудно показать что чисел этих хватит.
Получается наибольшее количество чисел 40.