Let \(p\) be a prime number. Show that if \(0 < r < p\) then the binomial coefficient \(\binom{p}{r}\) is divisible by \(p\). Let \(U(n, r)\) denote the remainder when \(\binom{n}{r}\) is divided by \(p\). Show that for \(0 < r < n\) we have \[U(n,r) = U(n-1,r-1)+U(n-1,r)-x,\] where \(x\) is either 0 or \(p\). Hence or otherwise prove that if \(m \geq 1\) and \(k \geq 1\), then \[U(p^km, r) = 0 \quad \text{if \(r\) is not a multiple of \(p^k\)},\] and \[U(p^km, p^ks) = U(m, s).\] [Hint: consider the case \(k = 1\) first.]
Define the determinant of a \(2 \times 2\) matrix \(C\) with complex entries, and show that \(C\) is invertible (i.e. has an inverse) if and only if its determinant is non-zero. Suppose \(C = A + iB\) is an invertible complex matrix, where \(A\) and \(B\) are real matrices. Prove that there exists a real number \(\lambda\) such that \(A + \lambda B\) is invertible, but show by an example that neither \(A\) nor \(B\) need be invertible. Two \(2 \times 2\) matrices \(P\) and \(Q\) are said to be conjugate if there exists an invertible matrix \(C\) such that \(Q = CPC^{-1}\). If \(P\) and \(Q\) are conjugate and have real entries, show that the matrix \(C\) may also be chosen to have real entries.
An integer-valued function \(f\) defined on the set of positive integers is said to be multiplicative if \(f(1) = 1\) and \(f(pq) = f(p) \cdot f(q)\) whenever \(p\) and \(q\) are coprime. Prove that if \(f\) and \(g\) are multiplicative functions, then so is the function \(f * g\) defined by \[f*g(n) = \sum_{d|n}f(d) \cdot g(n/d),\] where the sum is over all positive divisors \(d\) of \(n\) (including 1 and \(n\)). Let \(c(n) = 1\) for all \(n\), and let \(\varphi(n)\) denote the number of numbers in the set \(\{1, 2, \ldots, n\}\) which are coprime to \(n\) (where we adopt the convention that 1 is coprime to itself). By considering the set of all rational numbers \(m/n\) with \(1 \leq m \leq n\), prove that \[\varphi*c(n) = n\] for all \(n \geq 1\). Hence or otherwise prove that \(\varphi\) is a multiplicative function. [Hint: suppose not, and consider the least \(n\) such that \(\varphi(n) \neq \tilde{\varphi}(n)\), where \(\tilde{\varphi}\) is the unique multiplicative function agreeing with \(\varphi\) at prime powers.] Find an expression for \(\varphi(p^r)\), where \(p\) is a prime and \(r \geq 1\), and hence show that \[\varphi(n) = n \cdot \prod_{p|n} \left(1-\frac{1}{p}\right),\] where the product is over all distinct prime divisors of \(n\).
If \(S\) is a finite set of non-negative integers, we define \(\text{mex } S\) to be the least non-negative integer not in the set \(S\). (In particular if \(S\) is empty, we define \(\text{mex } S = 0\).) A binary operation \(*\) is defined inductively on the set \(N\) of non-negative integers by \[a * b = \text{mex}(\{a' * b: 0 \leq a' < a\} \cup \{a * b': 0 \leq b' < b\}).\] Assuming the result that \(*\) is associative, show by induction that \(N\) forms an abelian (i.e. commutative) group under \(*\), with identity element 0, in which every element is its own inverse. Show also that the set \(\{0, 1, 2, \ldots, a-1\}\) is a subgroup of \(N\) under \(*\) if and only if \(a\) is a power of 2, and that in this case \(a * b = a + b\) for all \(b < a\).
A spaceship is constructed by attaching the plane circular face of a hemisphere of radius \(a\), to the plane circular face at one end of a right circular cylinder of radius \(a\) and length \(b\). The angle between the axis of symmetry of the spaceship and the direction of the sun is \(\theta\). Show that the amount of solar heating is a maximum when \(\tan^2\theta = 16b^2/\pi^2a^2\), and find the value of \(\theta\) for which the amount of solar heating is a minimum. (You may assume that the amount of solar heating is proportional to the area of the shadow cast by the spaceship on a fixed plane.)
The functions \(x(t)\), \(y(t)\) satisfy the differential equations \[\frac{dx}{dt} = y - x,\] \[\frac{dy}{dt} = \begin{cases} y(1-x) & 0 < x < 1 \\ 0 & \text{otherwise} \end{cases}\] By considering the path \(\{x(t), y(t)\}\) traced out in the \((x, y)\) plane as \(t\) varies, show that the path starting at \((1, a)\), with \(0 < a < 1\), passes through (i) a point \((b, b)\), where \(0 < b < 1\), (ii) a point \((c, 1)\), where \(0 < c < 1\), and (iii) a point \((1, f(a))\), where \(f(a) > 1\). Show that \(f'(a) < 0\). By considering paths which cross the line \(y = 2x\), or otherwise, show that \(f(a) < 2\). Show that as \(t \to \infty\), \((x(t), y(t)) \to (f(a), f(a))\). [Hint: Do not attempt to solve the equations analytically in the region \(0 < x < 1\).]
In a class of students, feelings are running high. Those who are not friends are enemies. Every two students have precisely one friend in common. (a) Prove that if two students are enemies then they each have the same number of friends. (b) Prove that: either some student has no enemies, or any two students \(S\), \(S'\) can be 'linked by a hostile chain', that is, there are students \(S_1, S_2, \ldots, S_R\) so that each pair \((S, S_1)\), \((S_1, S_2)\), \(\ldots\), \((S_{R-1}, S_R)\), \((S_R, S')\) consists of enemies. (c) Deduce that if every student has some enemies then each student has the same number of friends.
A plane contains two fixed lines \(r\), \(s\) and two fixed points \(A\), \(B\) not lying on \(r\), \(s\). A variable point \(P\) lies on \(r\) (but not where \(AB\) meets \(r\)). Let \(AP\), \(BP\) meet \(s\) in \(A'\), \(B'\) respectively, and \(AB'\), \(BA'\) meet in \(Q\). Show that as \(P\) moves on \(r\), \(Q\) lies on a straight line through the point of intersection of \(r\) and \(s\).
\(P\) is the parabola \((x, y) = (at^2, 2at)\). (i) Prove that the normal to \(P\) at the point \(t\) is \[y + tx = 2at + at^3\] and that if \(Q\) is the point on \(P\) with parameter \(q\) then, provided \(q^2 > 8\), there are two normals from \(Q\) to \(P\) other than the normal at \(Q\). (ii) Let \(QR\), \(QS\) be the two normals from \(Q\) to \(P\); prove that as \(Q\) varies on \(P\) the chords \(RS\) pass through a fixed point. (iii) Show also that \(OQ\) and \(RS\) meet on a fixed line.
Let \(P\), \(Q\) be two points in the plane, distance 1 apart. Short rods \(PP'\), \(QQ'\), pivoted at \(P\) and \(Q\) respectively, are spun and come to rest at random. Let \(R\) be the point where the lines \(PP'\), \(QQ'\) meet when extended, and \(Y\) be the distance \(QR\). (i) Find the probability that \(Y\) is less than \(x\), for \(x \geq 0\). (You may leave your answer as an integral.) (ii) Calculate \(P(Y \leq 1)\).