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

Source paper: released examination archive.

Reduction of both coefficients in modular arithmetic givesMore explicitly,The first expression is divisible by $91$ exactly when the last parenthesis is. By the definition of a integer congruence, the two congruences are equivalent.

The Euclidean algorithm givesso $\gcd (754,91)=\gcd (26,91)=13$. Since $13\mid 39$, the criterion for a linear congruence guarantees a solution. One can also exhibit it directly: $26\cdot 5+91(-1)=39$, or in the original coefficients,Thus $x=5$ is a solution, with an explicit Bézout coefficient certificate.

Divide the divisibility relation $91\mid 26x-39$ by $13$ to obtain $7\mid 2x-3$. Since $2\cdot 4\equiv 1(\mathrm{mod}7)$, multiplication by the modular multiplicative inverse gives $x\equiv 12\equiv 5(\mathrm{mod}7)$. Therefore all integer solutions are $x=5+7q$, $q\in \mathbb{Z}$.

Modulo $91=13\cdot 7$, the choices $q=0,\dots ,12$ giveThey are distinct residue classes: equality of two such classes would imply $91\mid 7(q-q^{\prime })$, hence $13\mid q-q^{\prime }$. Every integer $q$ is congruent to one of those thirteen choices, so the list is exhaustive.

Let $d=\gcd (c,n)$, and write $c=d{c}^{\prime }$, $n=d{n}^{\prime }$ with positive integers $c^{\prime },n^{\prime }$. If an integer $e>1$ divided both $c^{\prime }$ and $n^{\prime }$, then $de$ would divide both $c$ and $n$, contradicting the maximality of their greatest common divisor $d$. Thus $\gcd (c^{\prime },n^{\prime })=1$. Equivalently, Bézout's identity for $c,n$ can be divided by $d$ to express $1$ as an integer combination of $c^{\prime },n^{\prime }$.

Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The preceding part gives $\gcd (c^{\prime },n^{\prime })=1$. The integer congruence on the left is equivalent toBy Euclid's lemma, coprimality of $c^{\prime }$ and $n^{\prime }$ makes this equivalent to $n^{\prime }\mid a-b$. The reverse implication is also immediate by multiplying a divisibility relation by $d{c}^{\prime }$. ThereforeThis is cancellation of a common factor in a congruence. The printed equality sign in the right-hand expression is interpreted as equality of residue classes, hence the displayed integer congruence. Ordinary equality of the integers $a,b$ would be false: the following example has $a\ne b$.

Take $(a,b,c,n)=(1,4,2,6)$. These are four distinct positive integers and $n\ge 3$. Their products are $ac=2$ and $bc=8$, whose difference is $6$, so $ac\equiv bc(\mathrm{mod}6)$. Here the correct reduced modulus is $6/\gcd (2,6)=3$, and indeed $1\equiv 4(\mathrm{mod}3)$. The example illustrates why cancelling a noninvertible factor may change the modulus in modular arithmetic.

For the base case $n=2$, the product is $1-1/4=3/4=(2+1)/(2\cdot 2)$. Assume the identity holds for some $n\ge 2$. Multiplying by the next factor givesThis is the desired expression with $n$ replaced by $n+1$, so mathematical induction proves the identity for every $n\ge 2$. The factorization $1-i^{-2}=(i-1)(i+1)/i^2$ also explains the cancellation as a telescoping product.

For $n=1$, both sides are $1/3$. Assuming the formula through $n$, adding the next term givesThe last expression is the required formula at $n+1$, completing mathematical induction. The partial fraction decompositionprovides a second explanation: this is a telescoping sum.

Suppose, for a proof by contradiction, that an integer $n$ is both an even number and an odd number. Then $n=2u$ and $n=2v+1$ for some integers $u,v$. Subtracting yields $u-v=1/2$. The left side is an integer, while $1/2$ is not. This contradiction proves that no integer is both even and odd.

The contrapositive is that an integer perfect square has residue $0$ or $1$ modulo $4$. Let $n=t^2$ for an integer $t$. If $t=2u$ is an even number, then $t^2=4u^2\equiv 0(\mathrm{mod}4)$. If $t=2u+1$ is an odd number, then $t^2=4u(u+1)+1\equiv 1(\mathrm{mod}4)$. These exhaust the possible parities of an integer. Thus a residue of $2$ or $3$ excludes being a perfect square, as required by the contrapositive.

Take $u=(1,1)$ and $v=(1,2)$. Their first coordinates are equal, so both $uRv$ and $vRu$ hold, although $u\ne v$. Thus $R$ is not an antisymmetric relation, and hence it is not a partial order. The failure arises because its comparisons ignore the second coordinate entirely.

Check each partial order axiom. For every $(a,b)$, $a\le a$ and $b\ge b$, so $S$ is a reflexive relation. If both $(a,b)S(c,d)$ and $(c,d)S(a,b)$, the first coordinates satisfy $a\le c\le a$ and the second coordinates satisfy $b\ge d\ge b$. Therefore $a=c$ and $b=d$, which proves $S$ is an antisymmetric relation.

Finally, if $(a,b)S(c,d)$ and $(c,d)S(e,f)$, then $a\le c\le e$ and $b\ge d\ge f$. Hence $(a,b)S(e,f)$, making $S$ a transitive relation. All three axioms hold, so $S$ is a partial order. It is a product order, with the usual order on the first coordinate and the reversed order on the second.

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

Use the standard spacing convention for machine epsilon: the next representable floating-point number above $1$ is $1+2^{-40}$. In a normalized binary representation this corresponds to $41$ significant binary digits, including the leading digit. The spacing throughout $[1,2)$ is therefore $2^{-40}$.

With rounding to nearest, the associated unit roundoff is half that spacing, $u=2^{-41}$; for a normal result the relative round-off error is bounded by $u$. Some texts instead call $u$ machine epsilon. Here $2^{-40}$ denotes the spacing scale, and the iteration counts below use that convention. It describes representation precision, not a guarantee that an arbitrarily evaluated function has a relative error this small.

The second-order remainder form of Taylor's theorem gives, for a point ${\xi }_x$ between $0$ and $x$,For $x\ne 0$, the given curvature bounds implyIn particular $f(1)<-1/2<0$ and $f(2)\ge 5>0$. Differentiability implies continuity, so the intermediate value theorem gives a root in $(1,2)$.

The mean value theorem applied to $f^{\prime }$ gives $f^{\prime }(x)=3+x{f}^{\prime \prime }({\eta }_x)\ge 3+2x>0$ for $x\in (1,2)$. Thus $f$ is strictly increasing there, and it cannot have two roots. There is exactly one root in $(1,2)$.

At a root of size between $1$ and $2$, the spacing of floating-point numbers is $ϵ=2^{-40}$. With ordinary stable function evaluations, a sensible generic absolute position tolerance has scale $2^{-40}\approx 9.09\times 10^{-13}$; sub-spacing progress cannot generally be represented. This is a resolution estimate, not a lower bound excluding an accidentally exactly representable root.

Define one bisection method step as replacing the current bracket by the half retaining the sign change. Starting from $[1,2]$, the width after $N$ such updates is $2^{-N}$. ThereforeThe midpoint of a bracket has an exact-arithmetic error bound of half its width. If tolerance is defined instead as that midpoint error bound, $39$ updates suffice to make it at most $2^{-40}$. Stating the convention avoids an off-by-one difference; once the endpoints are adjacent floating-point numbers, their exact midpoint need not itself be representable.

Apply the mean value theorem, the first-order case of Taylor's theorem, to $f^{\prime }$ between $0$ and $x>1$. It yieldsAlso $f(3/2)\ge -5+9/2+9/4=7/4>0$, so the initial point is to the right of the root $x^{\ast }$. For an increasing strictly convex function, its tangent at a point to the right of a root meets the axis between that root and the point. Hence the exact Newton root-finding iteration remains in $[x^{\ast },3/2]$ and decreases towards $x^{\ast }$.

On every relevant interval, $|f^{\prime \prime }|<3$ and $f^{\prime }>5$, so the stated quadratic convergence bound gives, with $e_n=|x_n-x^{\ast }|$,Iterating the bound givesThus four Newton corrections suffice to reduce the exact-iteration error bound below the floating-point spacing scale. The quadratic convergence doubles the approximate number of correct digits at each late step. Beyond this point further corrections cannot reliably improve a generic floating-point answer. This is a bound on useful accuracy under the usual stable-evaluation model, not a claim that the data specify the exact iteration at which every implementation must stagnate.

For negative $x$, the mean value theorem gives $f^{\prime }(x)=3+x{f}^{\prime \prime }({\xi }_x)$. In particular,Since $f^{\prime }$ is continuous and strictly increasing, it vanishes at exactly one point $x_m\in (-2,-1)$. The positive second derivative makes $f$ a strictly convex function on the entire real line. Its derivative changes from negative to positive at $x_m$, so $x_m$ is the unique global minimum. One may also use $f(x)\ge x^2+3x-5\to \infty$ to verify coercivity.

In the endpoint-bracketing form of golden-section search, begin with $[-2,-1]$, a width-one interval known to contain this unique minimum, and place the two standard interior probes. The attainable position accuracy is different from that for a simple root. Around $x_m$, Taylor's theorem givesHere the minimum value is nonzero and of order one: the lower quadratic bound gives $f(x_m)\ge -29/4$, while $f(x_m)\le f(-1)<-13/2$. Ordinary relative round-off error in these function values therefore hides changes of order $ϵ$, once $h^2$ has that size. The function-value resolution near a nondegenerate minimum is consequently of orderEach golden-section search contraction multiplies the bracket width by $\rho =(\sqrt{5}-1)/2$. Using $2^{-20}$ as the nominal target width givesUnknown evaluation-error constants can change the actual stopping point; $29$ is the standard scale-based count. Requiring $2^{-40}$ position accuracy from these function-value comparisons would disregard the quadratic flatness of the minimum. The same precision effect is documented for one-dimensional numerical minimization.^[ref]

Separate inactive and active optimization constraints. At an interior feasible point with $h>0$, a differentiable local minimum must satisfy $\nabla f=0$. Retain only solutions lying in the interior.

On the boundary $h=0$, if $\nabla h\ne 0$, apply the Lagrange multiplier condition. Using the optimization Lagrangian $L=f-\lambda h$, the Karush-Kuhn-Tucker conditions areThe sign follows from feasible motion into $h>0$: the directional derivative along $\nabla h$ at a minimum cannot be negative. Thus a boundary candidate has $h=0$ and a nonnegative Lagrange multiplier. Boundary points with $\nabla h=0$ must be examined separately, because the usual constraint qualification fails there.

Solve the interior and boundary systems, check membership in the feasible set, and establish which candidates are minima using second-order tests or a direct global comparison. The Karush-Kuhn-Tucker conditions alone are not sufficient for general nonconvex functions or feasible sets. On an unbounded feasible set, also check whether an infimum is attained and whether escaping sequences can improve the objective.

Complete the square to write the objective asLet $z=(x,y)$ and $a=(1,2)$, so $\Vert a\Vert =\sqrt{5}$ while feasibility requires $\Vert z\Vert \ge \sqrt{20}=2\sqrt{5}$. The reverse triangle inequality givesThe objective is therefore at least zero. Equality is attained by $z=2a=(2,4)$, which lies on the boundary. Equality requires the vectors to have the same direction and $\Vert z\Vert =2\sqrt{5}$, so this minimizer is unique. HenceIt also satisfies the Karush-Kuhn-Tucker conditions with $\lambda =1/2$. The direct distance argument proves global optimality even though the exterior of a disk is not a convex set; this is nearest-point minimization outside a Euclidean ball.

The objective is continuous on the compact disk, so a global maximum exists. Its gradient is $(e^x,2e^{2y})$, which is never zero, so a maximum cannot lie in the interior. It must have $x^2+y^2=1$.

Both coordinates of a maximizing point are positive. Reflecting a negative coordinate to its positive counterpart strictly increases the objective without changing the constraint; at an endpoint with one coordinate zero, a small move along the circle into the positive quadrant also increases the objective to first order. Thus it suffices to consider $x>0,y>0$.

The boundary Lagrange multiplier equations are $e^x=2\lambda x$ and $2e^{2y}=2\lambda y$. Eliminate $\lambda$ to obtain the two-dimensional nonlinear system of equationsKeeping this quadrant restriction excludes the boundary minimum that an unconstrained elimination could also produce. Under the stated uniqueness assumption for the admissible solution, the global maximum must be that solution. Approximate it with multivariable Newton iteration, solving $J_F(z_n){\Delta }_n=-F(z_n)$ and setting $z_{n+1}=z_n+{\Delta }_n$, with a suitable safeguard if needed. For example its explicit Jacobian matrix isNo numerical solution of the system is required.

Use the optimization LagrangianSymmetry gives the gradient equations $2Ax=\lambda 1$ and $2By=\lambda 1$. The positive-definite matrices are invertible, so defineThe affine constraint gives $\lambda =2/D$, henceFor a global certificate, write any other feasible point as $(x_{\ast }+u,y_{\ast }+v)$. Feasibility implies $1^{T}u+1^{T}v=0$. Expansion cancels the cross terms and leavesBy positive definiteness this is positive unless $u=v=0$. Thus the solution is the unique global minimum, not merely a stationary point. This is a two-block instance of positive quadratic minimization under one affine constraint.

Write $r=x-a$. The squared Euclidean norm is $r^{T}r$, whose gradient is $2r$. The chain rule for the exponential function therefore gives the column gradientThe row derivative, if that convention is used for $df/dx$, is its transpose.

Differentiate the column gradient $2e^{r^{T}r}r$. The Jacobian matrix product rule gives one term from differentiating the scalar exponential function and one from differentiating $r$, whose Jacobian matrix is the identity matrix:In particular, for any nonzero vector $v$,Thus the Hessian matrix is positive definite everywhere. This calculation proves strict convexity and supplies the derivatives needed for sums of these terms.

A practical choice is a BFGS method, using exact gradients and a line search. At dimension $d=100$, its $d$-by-$d$ inverse-Hessian matrix approximation is small, whereas forming a million rank-one contributions to the exact Hessian matrix is expensive. If $F(x)={\sum }_i{e}^{\Vert x-a_i{\Vert }^2}$, the explicit derivatives areThe positive-definite Hessian matrix and coercivity show that the objective has one global minimizer.

For numerical stability one can minimize $\Phi =\log F$ instead, which has exactly the same minimizer. Put $r_i=\Vert x-a_i{\Vert }^2$, $w_i=e^{r_i}/{\sum }_j{e}^{r_j}$, and $\bar{a}={\sum }_i{w}_i{a}_i$. Then the logarithmic gradient of an exponential squared-distance sum givesEvaluate the weights as $e^{r_i-r_{\max }}/{\sum }_j{e}^{r_j-r_{\max }}$ to avoid floating-point overflow. A Quasi-Newton method step iswhere $H_n$ is the positive-definite inverse-Hessian matrix approximation updated by BFGS, and ${\alpha }_n$ is chosen by a line search, for example one satisfying the Wolfe conditions. Under the standard smoothness and nondegeneracy assumptions at this strongly convex minimizer, full-memory BFGS has local superlinear convergence. An exact Newton's method in optimization would have local quadratic convergence, but pays for those much more expensive exact second derivatives.^[ref]

Here a dense $100000$-by-$100000$ matrix has $10^{10}$ entries, about $80$ GB even with eight-byte storage per entry. Use limited-memory BFGS on the negative of the objective, or equivalently its positive-definite approximate-metric form of gradient ascent. It stores only a fixed small number $\ell$ of vector pairs, costing $O(\ell d)$ memory rather than $O(d^2)$.

Let $G(x)={\sum }_{i=1}^{100}{e}^{e^{-\Vert x-a_i{\Vert }^2}}$ and put $c_i(x)=e^{e^{-\Vert x-a_i{\Vert }^2}}{e}^{-\Vert x-a_i{\Vert }^2}$. Direct use of the chain rule givesIf $H_n$ denotes the positive-definite inverse-Hessian matrix approximation for $-G$, the iteration iswith a line search increasing $G$ and the usual safeguarded limited-memory updates. No exact Hessian matrix is required. With fixed memory and the usual bounded-metric and line search hypotheses, expect local linear convergence near a nondegenerate strict maximum; fixed-memory limited-memory BFGS does not generally inherit the superlinear theorem for full-memory BFGS.

Unlike the preceding objective, $G$ is not generally a concave function. Thus this is a method for finding a local maximum; comparison of different converged candidates or a global search is needed to certify a global maximum for arbitrary centres. The symbolic problem supplies no assumption that would justify an unconditional global-convergence claim.^[ref]

Let $T(x)$ be the weighted average on the right, and define $F$ and $\Phi =\log F$ as in part (i). Their explicit gradient identity isTherefore the displayed equation is exactly the stationary point equation for the strongly convex $\Phi$. It has one solution, which is the unique minimizer from part (i). Reuse the BFGS iteration, withThe gradient is explicit, the weights can again be scaled by their largest exponent, and the usual full-memory BFGS assumptions give local superlinear convergence.

Simply setting $x_{n+1}=T(x_n)$ is not automatically a convergent fixed-point iteration. Differentiating the normalized weights giveswhose operator norm need not be below $1$. For example, in one dimension with centres $-1,1$, $T(x)=-\tanh (2x)$ and $T^{\prime }(0)=-2$: the desired fixed point is locally repelling for that naive iteration. If exact second derivatives are affordable, multivariable Newton iteration on $x-T(x)=0$ is another valid choice, with Jacobian matrix $I-J_T$ as given above and local quadratic convergence.

A general-purpose high-dimensional choice is Monte Carlo integration. Draw independent vectors $W_r$ uniformly from the unit cube and evaluate $H(W_r)={\sum }_{i=1}^{100}{e}^{\Vert W_r-a_i{\Vert }^2}$. The cube has volume $1$, so its integral is the expected value of $H(W_1)$. The iterative estimator isThe integrand is continuous on a compact set, hence bounded with finite variance. The strong law of large numbers gives almost sure convergence, and the square root of the mean squared error is exactly $\sigma /\sqrt{N}$, where ${\sigma }^2=\mathrm{Var}(H(W_1))$. Thus the standard stochastic accuracy rate is $O(N^{-1/2})$; the dimension affects the variance and evaluation cost, not this exponent.

There is also an important structure-specific improvement here: $e^{\Vert x-a_i{\Vert }^2}={\prod }_{j=1}^{100}{e}^{(x_j-a_{ij}{)}^2}$ is a separable integrand. The Fubini theorem reduces the requested value exactly toOne can therefore replace high-dimensional sampling by $10000$ one-dimensional composite Simpson's rule calculations. For each factor use even $n$, $h=1/n$, andthen iterate $n\leftarrow 2n$ and form the sum of the products. These smooth factors give $O(n^{-4})$ deterministic discretization error for fixed centres. Thus Monte Carlo integration is a valid generic answer, while exploiting separability is the more efficient specialized alternative; a large dimension alone does not force a tensor-product grid.

Let $A_i$ be the event that candidate $i$ succeeds. The countable additivity axiom adds probabilities only for mutually disjoint events. Successes of different candidates are not mutually exclusive, so replacing the probability of their union by ${\sum }_i\mathbb{P}(A_i)=1$ misuses that axiom. Without disjointness one obtains only the union bound, not certainty. The same sum is the expected value of the number of successes, which also need not imply at least one.

If the ten outcomes are mutually independent events, with each success probability $0.1$, all fail with probability $0.9^{10}$. HenceThe independence assumption is essential. The marginal probabilities alone allow any union probability from $0.1$ up to $1$; perfectly overlapping success events give the lower endpoint and disjoint successes give the upper endpoint.

The independent random variables have a product joint probability mass function. For integers $r,t\ge 0$,It is zero for all other pairs. The factors are the respective Poisson distribution masses, with the product justified by independence.

By the definition of a probability generating function and the power series for the exponential function,The series is absolutely convergent for every finite real $s$; in particular the expression is finite for all $s>1$, as needed for the later tail estimate.

For $Z=2(X+Y)+1$, independence givesThe initial factor $s$ accounts for the shift by one; substituting $s^2$ accounts for doubling the random variable. Its support consists of positive odd integers.

Conditioning on $Z=z$ has positive probability exactly when $z=2r+1$ for an integer $r\ge 0$. This is the same event as $X+Y=r$. The addition of independent Poisson random variables gives a Poisson distribution with parameter $\lambda +\mu$ for the sum. Therefore, for $0\le t\le r$,Thus $X\mid \{Z=2r+1\}\sim \mathrm{Binomial}(r,\lambda /(\lambda +\mu ))$. The case $r=0$ is a constant zero random variable. For even, nonpositive, or noninteger $z$, the conditioning event has zero probability, so an event-conditional probability distribution is not specified by the quotient formula. This is a two-component case of Poisson-multinomial conditioning.

Because $s>1$, the function $t\mapsto s^t$ is increasing and nonnegative. Thus $\{X\ge x\}=\{s^X\ge s^x\}$. Applying Markov's inequality to the nonnegative random variable $s^X$, whose expected value is finite by assumption, yieldsUnder the usual probability generating function convention $X$ takes nonnegative integer values. The argument itself works for any real random variable if $G_X(s)$ is understood as the finite expected value $\mathbb{E}[s^X]$.