Дима записывает в тетрадку в произвольном порядке натуральные числа от 2 до 42 включительно, каждое по разу.
Первое число он записывает синей ручкой.
Для каждого из последующих чисел Дима пользуется следующим правилом: если число, которое он собирается написать, является делителем хотя бы одного из ранее выписанных чисел или делится хотя бы на одно из них, то он записывает его красной ручкой, в противном случае синей.
Какое наибольшее количество чисел Дима может написать красной ручкой?
1 Ответ
Для того чтобы максимизировать количество чисел, записанных красной ручкой, Дима должен стратегически выбирать числа, которые он записывает.
Начинаем с самого большого числа, 42, записываем его синей ручкой. Затем все его делители (2, 3, 6, 7, 14, 21) и числа, которые делятся на 42 (нет таких в данном диапазоне), можно записать красной ручкой.
Затем выберем наибольшее число, которое ещё не записано, и которое не является делителем или кратным уже записанных чисел. Это 41 и мы записываем его синей ручкой. У 41 нет делителей в том диапазоне, которые мы не записали.
Затем перемещаемся к 40, он делится на 2, который уже записан, так что 40 записывается красной ручкой. Более того, все его делители (4, 5, 8, 10, 20) также могут быть записаны красной ручкой.
Следующий в списке не записанный неделимый — 39, и так далее.
Проделав эту процедуру для всех чисел до 2, получаем, что Дима сможет записать красной ручкой 35 чисел.