Technique
Largest subset with no two elements adding to a given total
Algebra • Sets
Statement
Let be a finite set and a number. Group the elements of into pairs with both in and ; every other element is left alone. A subset of in which no two different elements add to can hold at most one element from each pair, and it can hold every lone element. So the largest such subset has (number of pairs) (number of lone elements) elements, and taking one element from each pair together with all lone elements reaches it.
How to use it
- 1Write each element's partner and check whether the partner is in the set.
- 2An element equal to has no partner other than itself; a set holds it only once, so it is a lone element and can always be kept.
- 3The bound is the pigeonhole principle: one more element than the count would have to put two elements from the same pair into the subset.
Worked example
From , what is the largest number of elements that can be chosen so that no two chosen elements add to ?
Step-by-step
- 1Pairs:
— pairs Why: Each of these elements has its partner in the set.
- 2is alone, since
Why: It can only pair with itself, and a set holds it once.
- 3Largest choice , for example
Why: One from each pair plus the lone element; a ninth element would complete some pair.
Answer
Watch out
Count the element equal to as lone only when 'two elements' means two different elements; if a repeated element were allowed to count, it would have to be left out. Elements whose partner is missing from the set are also lone, and forgetting them gives an answer that is too small.
Also known as
pigeonhole pairing, complementary pairs, no two elements sum to, maximum subset without a forbidden sum, sum-free pairing, pair elements adding to a total