Задача
COM-B2-M04-P008 Максимальное непополняемое множество
В множестве \(\{1,2,\ldots,2n\}\) выбрано подмножество \(A\), к которому нельзя добавить ни одного нового числа так, чтобы в нём по-прежнему не было двух чисел с суммой \(2n+1\). Докажите, что \(A\) содержит ровно одно число из каждой пары \(\{1,2n\},\{2,2n-1\},\ldots,\{n,n+1\}\).
Сначала докажите, что из каждой пары взято не более одного числа, затем используйте невозможность добавить число.
В каждой паре \(\{i,2n+1-i\}\) нельзя взять оба числа, потому что их сумма равна \(2n+1\). Значит, из каждой пары взято не более одного числа.
Предположим, из некоторой пары не взято ни одного числа. Тогда можно добавить в \(A\) одно из чисел этой пары: его единственный партнёр по сумме \(2n+1\) тоже отсутствует. Условие не нарушится, что противоречит максимальности по включению.
Следовательно, из каждой пары взято ровно одно число.
Здесь важно различить «максимально по включению» и «наибольшего размера».