Polynomials \(C_r(x)\) are defined by \[C_0(x) = 1,\] \[C_r(x) = \frac{x(x-1) \ldots (x-r+1)}{r!} \text{ for } r \geq 1.\] (i) Show that if \(n\) is an integer, then so is \(C_r(n)\). (ii) Show that any polynomial \(p(x)\) with rational coefficients can be expressed in the form \[b_kC_k(x)+b_{k-1}C_{k-1}(x)+ \ldots +b_0C_0(x),\] where all the \(b_r\)'s are rational and \(k\) is the degree of \(p(x)\). Suppose further that whenever \(n\) is an integer, then so is \(p(n)\). Show that all the \(b_r\)'s are integers. (iii) Suppose that \(p(x)\) is a polynomial with real coefficients such that whenever \(a\) is a rational number then so is \(p(a)\). Show that the coefficients of \(p(x)\) are all rational.
Find necessary and sufficient conditions on the coefficients of the recurrence relations \[u_{n+2} = au_{n+1} + bu_n,\] \[v_{n+2} = cv_{n+1} + dv_n\] to ensure that, if \(u_0, u_1, v_0, v_1\) are arbitrary subject to \(v_0 = u_0\) and \(v_1 = u_2 = au_1 + bu_0\) then, for all \(n\), \[u_{2n} = v_n.\] Let \(v_n\) be defined by \(v_0 = 1, v_1 = 1, v_{n+2} = kv_{n+1} - v_n\). Show that, if \(k \geq 3\), then \[v_n \geq (\sqrt{k-2}+1)^{n-1}.\]
What is the order of the smallest non-commutative group? Prove that there is, up to isomorphism, only one such group of that order. Carefully justify your answers.
(i) \(X, Y\) and \(Z\) are positive numbers. Prove that \[(Y+Z-X)(Z+X-Y)(X+Y-Z) \leq XYZ.\] (ii) \(z_1, z_2...z_n\) are complex numbers and \(\omega = (z_1 + z_2... + z_n)/n\). Prove that, for any complex number \(z\), \[\sum_{i=1}^{n} |z-z_i|^2 \geq n|z-\omega|^2.\]
A Euclidean motion \(M\) of the plane is a transformation of the plane onto itself of the form of a rotation or reflection followed by a translation (so that distance and angle are preserved). Some construction is given whereby from any set of \(n\) distinct points \(A_1, ..., A_n\) a point \(P\) (respectively a line \(l\)) is obtained. The construction is called geometric for \(A_1, ..., A_n\) if (i) \(P\) (respectively \(l\)) does not depend on the order of the points \(A_1, ..., A_n\), and (ii) for any Euclidean motion \(M\) the given construction applied to the points \(M(A_1), ..., M(A_n)\) yields \(M(P)\) (respectively \(M(l)\)). Determine (a) all geometric point constructions, and (b) all geometric line constructions, for a pair of distinct points \(A, B\). By considering symmetric configurations, or otherwise, show that there are no geometric line constructions for \(n\) points if \(n \geq 3\). Exhibit, however, a geometric point construction for \(n\) points.
A set of points in the plane is \(k\)-distant if the distances \(d(A_i, A_j)\) (\(i \neq j\)) take precisely \(k\) distinct values. Thus the 1-distant sets consist of two points or are the vertices of an equilateral triangle. Given an equilateral triangle \(ABC\) determine all possible 2-distant sets containing \(A, B, C\). Deduce that a 2-distant set has at most 5 points.
Let \(f\) be a continuous function on \([0, \infty)\) which is increasing (that is, if \(x \leq y\) then \(f(x) \leq f(y)\)). For \(s \geq 0\) define \(F(s) = \int_0^s f(x)dx\). Show that for \(s \geq 0, t \geq 0, 0 < \lambda \leq 1\), \[F(\lambda s + (1 - \lambda)t) \leq \lambda F(s) + (1 - \lambda)F(t).\] Suppose \(g\) is a continuous increasing function on \([0, \infty)\) such that \(g(f(x)) = x\) and \(f(g(y)) = y\), and hence \(f(0) = g(0) = 0\). For \(t \geq 0\), define \(G(t) = \int_0^t g(y)dy\). Demonstrate by means of a diagram that for \(s \geq 0\) and \(t \geq 0\), \[F(s) + G(t) \geq st.\] Show that, for non-negative \(a\) and \(b\), \[a^{\frac{1}{3}}b^{\frac{2}{3}} \leq \frac{1}{3}a + \frac{2}{3}b \leq \log(e^a + 2e^b) - \log3.\]
(i) By considering \(A(1 + \eta - x^2)^n\) for suitable values of \(A, \eta\) and \(n\), show that, given \(\epsilon > 0\) and \(0 < \beta < \alpha < 1\), we can find a polynomial \(P(x)\) such that \[P(x) \geq 1 \text{ for } |x| \leq \beta,\] \[0 \leq P(x) \leq 1 \text{ for } \beta \leq |x| \leq \alpha,\] \[0 \leq P(x) \leq \epsilon \text{ for } \alpha \leq |x| \leq 1.\] (ii) Show that, given \(\epsilon > 0\), there is a polynomial \(Q(x)\) such that \[|Q(x)| \leq \epsilon \text{ for } -1 \leq x \leq -\epsilon,\] \[-\epsilon \leq Q(x) \leq 1+\epsilon \text{ for } -\epsilon \leq x \leq \epsilon,\] \[|Q(x)-1| \leq \epsilon \text{ for } \epsilon \leq x \leq 1.\] (iii) Show that, given \(\epsilon > 0\) and \(0 < a \leq 1\), there is a polynomial \(R(x)\) such that \[|R(x)| \leq \epsilon \text{ for } a \leq |x| \leq 1,\] \[|R(x)-(1-a^{-1}|x|)| \leq \epsilon \text{ for } |x| \leq a.\]
A mouse \(M\) is running at a constant speed \((U, 0)\) along the line \(y = 0\). At \(t = 0\), the mouse is at position \((a, 0)\), where \(a > 0\), and a cat \(C\) is at \((0, b)\). The cat starts running at constant speed \(V\) in a direction which is always towards the mouse. If \(O\) is the origin and \(\psi\) the acute angle \(OMC\), show that \[\frac{d}{dt}(\cot \psi) = \frac{U}{y},\] where \((x, y)\) is the position of \(C\) at any time \(t\). If \(b \ll a\), show that the path of \(C\) is given approximately, for \(t > 0\), by an equation of form \[x = Ay^{1-\lambda} + B,\] where \(A\) and \(B\) are constants to be found and \(\lambda = U/V\), provided \(\lambda > 1\). Find the approximate equation of the path when \(\lambda = 1\).
Craps is played between a gambler and a banker as follows. On each throw, the gambler throws two dice. If his first throw is 7 or 11 he wins and if it is 2, 3 or 12 he loses. If his first throw is none of these he throws repeatedly until either he again throws the same as his first throw, in which case he wins, or he throws a 7, in which case he loses. What is the probability that he wins?