Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 15 2 iii Solution Created 2026-10-03 Updated 2026-10-14
Translate each two-element set by its smaller element to write with . Translation does not affect any sumset cardinality. The pair-sum hypothesis forces the to be distinct, since equal values would give only three pair sums. Relabel so .
The distinct-positive-integer subset-sum lower bound has a short inductive proof. Suppose the first values have sum , their largest subset sum. Adding creates the distinct sums and for . They are all above , since , and hence are all new. Starting with one sum for no elements and adding new sums givesEquality is attained by . Their subset sums fill every integer from zero to , by induction on , and each pair of distinct positive values has four different pair sums. Thus the bound is best possible for every .