Вася разбивает на пары натуральные числа от 1 до 22 и подсчитывает количество пар, в которых одно из чисел делится на другое. Какой наибольший результат получится?

Ответ: 10 пар.

Чтобы решить задачу, нужно доказать, что больше 10 пар получить нельзя, а затем показать пример разбиения, в котором ровно 10 пар удовлетворяют условию.

1. Докажем, что больше 10 пар быть не может

Всего у Васи 22 натуральных числа — от 1 до 22. Значит, он должен разбить их на 11 пар.

Обратим внимание на числа 13, 17 и 19.

Все три числа простые, причём их удвоенные значения больше 22. Поэтому среди чисел от 1 до 22 каждое из них может образовать пару, в которой одно число делится на другое, только с числом 1.

Но число 1 можно использовать лишь в одной паре!

Следовательно, невозможно составить 11 пар, в каждой из которых одно число делится на другое. Хотя бы одна пара обязательно не будет удовлетворять условию.

Значит, количество подходящих пар не превосходит:

2. Покажем, что 10 пар действительно можно получить

Разобьём числа следующим образом:

Мы использовали все числа от 1 до 22 ровно по одному разу.

Получилось 11 пар, из которых 10 удовлетворяют условию, а одна — нет.

3. Вывод

Мы доказали, что получить больше 10 подходящих пар невозможно, и привели пример разбиения, в котором таких пар ровно 10.

Следовательно, наибольший возможный результат Васи равен