Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 3 / d / Solution

Fix any seven-element subset $S$. Its power set supplies $2^7=128$ pigeons. Map each subset to its integer sum. Since the elements are positive, all such sums lie between $0$ and ${\sum }_{s\in S}s$. The latter is at most the sum of the seven largest available elements,There are therefore at most $92$ possible sums, fewer than the $128$ subsets. The pigeonhole principle forces two distinct subsets to have the same sum. Every seven-element subset has the two-sum property. This is the subset-sum pigeonhole bound. The weaker estimate ${\sum }_{s\in S}s\le 7\cdot 16=112$ would also suffice, since $128>113$.