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

A subset is determined uniquely by deciding, for each of the $n$ elements, whether to include it. Each decision has two possibilities. By the rule of product, there are $2\cdot 2\cdots 2=2^n$ decision strings. The correspondence between such binary strings and subsets is a bijection, so $|\mathcal{P}(\mathcal{U})|=2^n$. The all-zero string corresponds to the empty subset.

For $q\ge 1$, choose an ordered list of $q$ distinct elements: there are $n(n-1)\cdots (n-q+1)$ such lists. Every $q$-element subset occurs in exactly $q!$ orders, the number of permutations of its elements. Thus the count is the binomial coefficientFor fixed $q$ and $n\ge 2q$, every numerator factor lies between $n/2$ and $n$. ConsequentlyThe constants depend on the fixed $q$, not on $n$. These inequalities prove $\left(\genfrac{}{}{0ex}{}{n}{q}\right)=\Theta (n^q)$ in big theta notation. More precisely, dividing the product by $n^q$ gives the fixed-cardinality binomial coefficient asymptotic $\left(\genfrac{}{}{0ex}{}{n}{q}\right)\sim n^q/q!$. For $q=0$, there is exactly one empty subset, and the assertion is $1=\Theta (1)$.

For $q=1,\dots ,5$, choose the first $q$ elements of $\{1,2,4,8,16\}$. 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 $0$ through $5$.

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$.

The number isA direct search over every $q$-element subset must inspect $\left(\genfrac{}{}{0ex}{}{n}{q}\right)$ candidates. Testing one candidate by generating its subset sums creates $2^q$ values; storing previously seen sums detects a collision. Generating them incrementally needs $O(2^q)$ arithmetic operations, or $O(q{2}^q)$ for the straightforward independent calculation of each sum. Thus the simple overall search has cost on the scale of $\left(\genfrac{}{}{0ex}{}{n}{q}\right)2^q$, apart from integer-arithmetic and data-structure costs.

The important time complexity distinction is that fixed $q$ gives polynomial growth in $n$, of degree $q$, but this can still become impractically large. If $q$ increases with $n$, both the candidate count and the internal power set can grow exponentially. For example, near $q=n/2$ the binomial coefficient is already exponentially large. An exhaustive implementation can therefore encounter a combinatorial explosion; the fixed-$q$ estimate $\Theta (n^q)$ must not be described as exponential in $n$.