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

We prove the contrapositive. If $3\nmid a$, Euclidean division gives $a=3q+1$ or $a=3q+2$ for an integer $q$. Squaring gives respectively $a^2=3(3q^2+2q)+1$ or $a^2=3(3q^2+4q+1)+1$. Both have remainder $1$ upon division by $3$, so $3\nmid a^2$. Taking the contrapositive yields $3\mid a^2\Rightarrow 3\mid a$.

For a proof by contradiction, suppose $\sqrt{3}=a/b$ for positive integers $a,b$ in lowest terms, so $\gcd (a,b)=1$. Squaring gives $a^2=3b^2$, and part (a) implies $3\mid a$. Write $a=3c$; then $9c^2=3b^2$, hence $b^2=3c^2$, and part (a) again implies $3\mid b$. This contradicts the coprimality of $a,b$. Therefore $\sqrt{3}$ is an irrational number.

The fifty disjoint sets $\{1,100\},\{2,99\},\dots ,\{50,51\}$ form a partition of a set $\{1,\dots ,100\}$. If a chosen subset met each pair at most once, it would contain at most fifty elements. The pigeonhole principle therefore forces a $51$-element subset to contain both elements of at least one pair. Those two distinct elements sum to $101$.

Assume $n\ge 1$ and list the elements of $X$ as $a_1,\dots ,a_n$. Define the partial sums $s_j=a_1+\cdots +a_j$ for $1\le j\le n$. If one is divisible by $n$, its corresponding nonempty prefix is a suitable $Y$.

Otherwise the $n$ partial sums have remainders in the $n-1$ nonzero residue classes. The pigeonhole principle gives $i<j$ with $s_i\equiv s_j(\mathrm{mod}n)$. Thus $s_j-s_i=a_{i+1}+\cdots +a_j$ is divisible by $n$, giving a nonempty subset $Y=\{a_{i+1},\dots ,a_j\}$.

Therefore a nonempty $Y$ exists. This strengthens the literal assertion, which would otherwise allow the trivial empty set with sum zero.

Since $h(n)=\max \{f(n),g(n)\}$, both $f(n)\le h(n)$ and $g(n)\le h(n)$. Therefore $f(n)+g(n)\le 2h(n)$ for every positive $n$. The definition of big O notation is satisfied with constant $2$ and threshold $1$. True: $f+g=O(h)$.

Positivity gives $\max \{f(n),g(n)\}\le f(n)+g(n)$. Thus $h(n)\le f(n)+g(n)$ for every positive $n$, meeting big O notation with constant $1$ and threshold $1$. True: $h=O(f+g)$.

Take $f(n)=g(n)=n^2$, so $h(n)=n^2$ but $(f\circ g)(n)=n^4$. The ratio $(f\circ g)(n)/h(n)=n^2$ is unbounded, precluding any eventual constant upper bound in big O notation. False: in general $f\circ g\ne O(h)$. This is a counterexample involving function composition, not pointwise addition.

For each fixed positive integer $k$, part (i) gives $(f(n)+g(n){)}^k\le (2h(n){)}^k=2^{k}h(n{)}^k$. This meets big O notation with constant $2^k$ and threshold $1$. True: $(f+g{)}^k=O(h^k)$ for fixed $k$. The constant may depend on $k$; no claim uniform in a varying $k$ is required.

Prove the explicit bound $n!\le 2^{n^2}$ by mathematical induction. At $n=1$, $1\le 2$. For the step, note that $n+1\le 2^n$ for $n\ge 1$: this auxiliary inequality has base $2=2$ and follows at the next index from $n+2\le 2(n+1)$. Hence, using the induction hypothesis,Thus $n!=O((2^n{)}^n)$, with constant $1$ and threshold $1$ in big O notation.

We prove the stronger explicit bound $n!\le n^n/2^{n-1}$ by mathematical induction. The case $n=1$ is equality. The binomial theorem gives $(1+1/n{)}^n\ge 1+n/n=2$, so $(n+1{)}^n\ge 2n^n$. Consequently the induction hypothesis yieldsTherefore $n!=O(n^n/2^n)$, with constant $2$ and threshold $1$.

The second bound is asymptotically tighter. Using $n\le 2^n$,Thus its bounding function is negligible relative to the first in little o notation; this compares the bounds without needing Stirling's formula.