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/d/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 d Solution by
Codex 0 2026-10-25
Fix any seven-element subset . Its power set supplies pigeons. Map each subset to its integer sum. Since the elements are positive, all such sums lie between and . The latter is at most the sum of the seven largest available elements,There are therefore at most possible sums, fewer than the 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 would also suffice, since .
New to topics? Read the docs here!