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

The integer congruence $x\equiv y(\mathrm{mod}n)$ means $n\mid (x-y)$: the difference is an integer multiple of the positive modulus $n$. Write $x_1-x_2=na$ and $y_1-y_2=nb$ for integers $a,b$. Thenso addition preserves integer congruence. For multiplication,The final coefficient is an integer, so multiplication also preserves integer congruence. These properties make addition and multiplication well defined on residue classes.

The Euclidean algorithm givesThe last nonzero remainder is $g=92$. Back-substitution produces its Bézout coefficients:Thus $(m,n)=(-8,11)$ is a requested pair. The final equality independently checks the calculation.

The pigeonhole principle states that if more than $r$ objects are placed in $r$ boxes, with $r\ge 1$, at least one box contains two or more objects. Equivalently, a function from a finite set of more than $r$ elements to a set of $r$ elements cannot be injective: if every box held at most one object, there would be at most $r$ objects altogether.

For five points, partition the unit square into four squares of side $1/2$. Assign boundary points to just one neighbouring piece. By the pigeonhole principle, two of the points lie in one piece, whose diameter is its diagonal, $\sqrt{(1/2{)}^2+(1/2{)}^2}=\sqrt{2}/2$.

For eight points, use seven smaller-diameter pieces rather than eight rectangles. Start with the convex pentagonTake its four reflected copies at the corners of the square. The remaining pieces are the left triangle with vertices $(0,1/4),(1/4,1/2),(0,3/4)$, its right-hand reflection, and the central diamond with vertices $(1/4,1/2),(1/2,1/4),(3/4,1/2),(1/2,3/4)$. These seven polygons cover the square with disjoint interiors. To verify coverage directly, for $0\le y\le 1/4$ the two bottom pentagons split the horizontal section at $x=1/2$. For $1/4\le y\le 1/2$, the five successive sections have endpoints $0,y-1/4,3/4-y,y+1/4,5/4-y,1$ and belong respectively to the left triangle, bottom-left pentagon, diamond, bottom-right pentagon and right triangle. Reflection gives the top half.

The diameter of a finite convex hull is the greatest distance between its vertices: if two points are convex combinations of vertices, their difference is a convex combination of vertex differences, and the triangle inequality bounds its norm by the largest such distance. Checking the five vertices of $P$ gives diameter $\sqrt{(1/2{)}^2+(1/4{)}^2}=\sqrt{5}/4$; reflections preserve that value. Each remaining triangle and the diamond has diameter $1/2$, which is smaller. After assigning shared boundaries to one piece, eight points in these seven pieces force a pair in a common piece. Hence some pair is at distance at most $\sqrt{5}/4$.

Both arguments are instances of a pigeonhole distance bound from a partition.

Prove the stronger statement with a nonempty subset. Order the $n\ge 1$ integers as $a_1,\dots ,a_n$, and form the prefix sumsThere are $n+1$ such sums but only $n$ residue classes modulo $n$. The pigeonhole principle gives indices $0\le i<j\le n$ with $s_i\equiv s_j(\mathrm{mod}n)$. Their difference satisfiesThe selected elements form a nonempty subset of $S$, proving the claim. Neither positivity nor distinct values in a general ordered sequence are needed for the consecutive sum divisible by the sequence length argument; distinctness merely makes the present input a set.