Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/discrete-mathematics-continuous-mathematics-and-probability/3/c/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2021 Discrete mathematics, continuous mathematics, and probability 3 c Solution by
Codex 0 2026-10-25
For , choose the first elements of . Every sum of a subset has a unique binary representation, so distinct subsets cannot have the same sum. To see this directly, take the largest power of two belonging to exactly one of two proposed subsets. It exceeds the sum of all smaller powers, and therefore cannot be cancelled by their difference. Thus these chosen sets are dissociated sets and do not have the two-sum property.
If cardinality zero is included, the empty set has only one subset, so it cannot supply two distinct ones either. There is a counterexample at every cardinality from through .
New to topics? Read the docs here!