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

Use modular arithmetic modulo eight: $801\equiv 1$, $32\cdot 19\equiv 0$, and $29\cdot 13\equiv 5\cdot 5\equiv 1$. The squared difference is consequently congruent to one, giving the remainder

Modulo seven, $19\equiv -2$ and $(-2{)}^3=-8\equiv -1$. Therefore $19^9\equiv (-1{)}^3\equiv -1\equiv 6(\mathrm{mod}7)$. The remainder is $6$, using modular exponentiation.

For integers $a,b$ not both zero, replace them first by their absolute values, then repeat integer division:

while b != 0:
    (a,b) := (b, a mod b)
return a

This is the Euclidean algorithm. Its loop invariant is that $\gcd (a,b)$ equals the original greatest common divisor. When $b>0$, the new remainder lies in $[0,b)$, so $b$ is a strictly decreasing nonnegative loop variant. At termination, $\gcd (a,0)=a$, proving correctness, including the case where one original input is zero.

The Euclidean algorithm givesThus the greatest common divisor is $34$. Back-substitution, as in the extended Euclidean algorithm, givesHence $\gcd (306,1394)=34$, with $x=2$ and $y=-9$.

For one colour, the box occupancies form a weak composition of $k$ into $n$ nonnegative parts. For $n\ge 1$, stars and bars gives $\left(\genfrac{}{}{0ex}{}{k+n-1}{n-1}\right)$ choices. The three colours' occupancies can be selected independently, so the number isBoxes are labelled, while equal-colour balls contribute only occupancy counts; no extra factorial for permuting such balls is appropriate.

There are $6^3=216$ unrestricted placements, since one colour has $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ occupancy vectors. For any specified empty box, the two remaining boxes admit $3^3=27$ placements. For any specified pair of empty boxes, the one remaining box admits one placement. All three boxes cannot be empty.

The inclusion-exclusion principle therefore givesThe empty-box events are not disjoint events, so subtracting their counts without restoring their pairwise overlaps would be incorrect.

The base cases are $13=3(2)+7(1)$, $14=3(0)+7(2)$ and $15=3(5)+7(0)$. Suppose a counterexample exists and choose the least integer $n\ge 13$ failing the claim. It is not one of these base cases, so $n\ge 16$ and $n-3\ge 13$.

Minimality supplies nonnegative integers $x,y$ with $n-3=3x+7y$. Then $n=3(x+1)+7y$, a contradiction. This proof by minimal counterexample establishes the claim. Three consecutive base cases are needed because the reduction subtracts three.