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.

Answer 2

Для решения этой задачи требуется выбрать несколько чисел из набора натуральных чисел от 1 до 104 и расположить их по кругу таким образом, чтобы произведение любых двух соседних чисел делилось на 40. Необходимо определить наибольшее количество чисел, которое можно выбрать.

Решение:

Чтобы произведение двух соседних чисел делилось на 40, необходимо, чтобы каждое из этих чисел делилось на 40 или имело общий множитель с 40. Разложим число 40 на простые множители: 40 = 2 * 2 * 2 * 5.

Теперь рассмотрим каждый из простых множителей по отдельности.

1. Множитель 2: Чтобы произведение двух соседних чисел делилось на 2, достаточно, чтобы каждое из этих чисел было четным. В наборе чисел от 1 до 104, половина чисел являются четными (52 числа). Поэтому можно выбрать максимум 52 числа, которые делятся на 2.

2. Множитель 5: Чтобы произведение двух соседних чисел делилось на 5, достаточно, чтобы каждое из этих чисел было кратным 5. В наборе чисел от 1 до 104, каждое пятое число является кратным 5 (20 чисел). Поэтому можно выбрать максимум 20 чисел, которые делятся на 5.

Таким образом, наибольшее количество чисел, которое можно выбрать, равно 52 + 20 = 72.

Ответ:

Максимальное количество чисел, которое можно выбрать из набора натуральных чисел от 1 до 104 и расположить их по кругу так, чтобы произведение любых двух соседних чисел делилось на 40, составляет 72 числа.