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

Рассмотрим задачу: у нас есть числа от 1 до 22, их нужно разбить на пары так, чтобы в каждой паре одно число делилось на другое. Каждое число можно использовать только один раз. Нужно найти максимально возможное число таких пар. Общее понимание: - Каждая пара \((a, b)\), где \(a\) делится на \(b\), то есть \(\frac{a}{b}\) — целое число. - Не обязательно, чтобы в паре было \(a > b\) или \(b > a\). Важно только, чтобы делимость выполнялась. Обычно, чтобы было удобно, рассматривать пары так, чтобы меньший число делилось на большее, или наоборот, — нужно выбрать удобную стратегию. Подход к решению: Чтобы максимизировать число пар, нужно как можно большее количество чисел связать в допустимых парах. Мысленно, лучше всего — сформировать максимально возможное количество «маленьких» делителей, которые делятся на меньшие числа, и так далее. Рассмотрим стратегию: - Назовем «делящийся» число — число, которое делится на какое-то другое число из набора. - Нам нужно максимально часто использовать числа как делители, т.е. искать возможность собрать много пар, где одно число — делитель другого. Интуитивное решение: - Самое маленькое число 1 делится на всё (0 — не интересно), поэтому желательно использовать 1 как делитель для больших чисел, чтобы получить много пар. - Также стоит обратить внимание на числа, у которых есть делители среди чисел меньших их. Проще всего — рассортировать числа по делимостью. - Начнем с 1: он делит все числа, кроме самого 1. Это значит, что с 1 можно образовать пары: (1,2), (1,3), ..., (1,22). Но каждое число может участвовать только один раз. Значит, мы можем использовать 1 только для одной пары — например, с 2. - После этого остается 1 и все остальные числа, кроме тех, с которыми уже сформирована пара. Но важно помнить, что чтобы получить максимальное число пар, лучше всего — связать как можно больше пар с помощью делимости, избегая потерь. Рассмотрим конкретный пример: - Какие пары возможны? Например: - 2 делится на 1 → пара (2,1) - 3 делится на 1 → (3,1) - 4 делится на 2 → (4,2) - 6 делится на 3 → (6,3), также, например, 6 делится и на 2 → (6,2), но чтобы максимизировать число пар, желательно избегать повторных связей к одному числу. Оптимальный план — построить так называемую «цепочку» или «сетку» таких делимых пар, выбирая для каждого числа делитель или делимое, чтобы не пересекаться. Для этого лучше всего — рассмотреть все возможные делители и посчитать, сколько пар можно сформировать. --- ### Решение поэтапно: 1. **Обозначим:** - Множество чисел: \( \{1, 2, 3, ..., 22\} \). 2. **Пары, где меньшее число делит большее:** - Например: (1,2), (1,3), ..., (1,22) - *(Но мы можем использовать только одну такую пару, потому что 1 может участвовать только в одной паре или в нескольких?)* — Каждое число только один раз, так что только одна пара с 1 возможна. 3. **Обеспечим максимальность:** - Попытаемся найти такую разметку, которая позволяет сформировать как можно больше пар. --- ### Идея: - Распределим числа по делителям. - Для чисел от 2 до 22 каждому ищем делителя, который уже используется или можем выбрать. - Например, делим числа по их делителям: | Делитель | Множество чисел, делящихся на него | |------------|-------------------------------------| | 1 | 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22 | | 2 | 4,6,8,10,12,14,16,18,20,22 | | 3 | 6,9,12,15,18,21 | | 4 |8,12,16,20 | | 5 |10,15,20 | | 6 | 12,18 | | 7 |14,21 | | 8 |16,24 (нет 24, значит 16)| | 9 |18 | И так далее. --- ### Решение: Чтобы сформировать максимум пар, можно построить цепочку: - Начинаем с максимальных делителей, например, 22 (делится на 1 только), затем ищем числа, которым он делится или делят его. Но проще — взять число 1: оно делит все, он может участвовать только в одной паре. Следовательно, оптимально — использовать делимость в «цепочках»: - Образуем пары так, чтобы вызвать максимальное количество связей: Например: - (2,1) — делитель 1 и 2 - (3,1) - (4,2) - (6,3) - (8,4) - (12,6) - (24,8) — но 24 нет, так что продолжать с 8 → дальше 16, 20, 22 и т.д. Но так как каждое число может входить только в одну пару, задача — подобрать максимально возможное число таких связей. --- ### Итоговое решение: Чтобы максимально получить таких пар, лучше всего — выбрать в качестве делителей числа, у которых много кратных, и построить цепи: - Например, pairing: | Делитель | Кратные | |------------|---------| | 2 | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22 | | 3 | 6, 9, 12, 15, 18, 21 | | 4 | 8, 12, 16, 20 | | 5 | 10, 15, 20 | - Выбираем пары путем сопоставления кратных с делителями, избегая пересечений. --- ### Итог: На практике, такой тип задач используют жадный алгоритм: - Сначала сортируем числа. - Постараемся pair их так, чтобы максимально использовать делимость. Запишем пример возможных пар: - (2,1) - (3,1) - (4,2) - (6,3) - (8,4) - (9,3) - (10,5) - (12,6) - (14,7) - (15,3) - (16,8) - (18,9) - (20,10) - (21,7) - (22,11) И так далее. Учтя, что каждое число можно использовать только один раз, максимальное число пар — это количество чисел, которые могут быть связаны в цепь делимости, то есть примерно приятное число — около 11. --- ### **Ответ:** Максимально возможное количество пар — **11**. --- Если нужно точное решение или подтверждение, можно составить конкретный пример, разбить числа последовательно, или использовать алгоритм поиска максимального паросочетания в графе. --- Если есть дополнительные вопросы — спрашивайте!