Problems

In a tournament everybody played against everybody else exactly once, and no game ended in a draw. Show that it is possible to order the players in such a way that everybody beat the player coming immediately after him in the ordering. Show also that if no player beat all the others then there are at least three such orderings.

The bus routes in a town have the following properties.

1. [(i)] Any two bus stops are connected by a bus route.
2. [(ii)] Every two different bus routes have exactly one common bus stop.
3. [(iii)] On each bus route there are exactly \(n\) (\(\geq 2\)) bus stops.

If the town has at least two bus routes how many bus stops are in the town? How many bus routes are there? [For the purpose of this problem the term 'bus stop' includes any terminals.]

Let \(G\) be a group of permutations of a finite set \(X\). Define the stabiliser \(H(\alpha)\) of \(\alpha \in X\) by \[H(\alpha) \equiv \{g:g \in G, g\alpha = \alpha\}.\] The orbit of an element \(\alpha \in X\), \(O(\alpha)\), is the set of elements \(y\) in \(X\) such that \(g\alpha = y\) for some permutation \(g \in G\). Prove the following statements:

1. [(i)] For any \(\alpha \in X\), \(H(\alpha)\) is a subgroup of \(G\).
2. [(ii)] If \(\alpha, \beta \in X\), \(O(\alpha)\) and \(O(\beta)\) either coincide, or they are disjoint.
3. [(iii)] \(|O(\alpha)| \cdot |H(\alpha)| = |G|\), where \(|A|\) denotes the number of elements of a set \(A\).

Let \(n\), \(p\) and \(q\) be integers and suppose that \(1 < p/q < \sqrt[n+1]2\). Prove that \[\sqrt[n+1]2 < \frac{p^n + p^{n-1}q + ... + pq^{n-1} + 2q^n}{p^n + p^{n-1}q + ... + pq^{n-1} + q^n} = r, \quad \text{say},\] and show that \(r\) is a better approximation to \(\sqrt[n+1]2\) than \(p/q\) is.

The vertices \(A\), \(B\), \(C\) of a triangle (which may be assumed not to be right-angled) are given, referred to a suitable origin, by the vectors \(\mathbf{a}\), \(\mathbf{b}\), \(\mathbf{c}\). Show that the vector positions of the orthocentre \(H\) and the circumcentre \(S\) of the triangle are given by \[(\alpha + \beta + \gamma)\mathbf{h} = \alpha\mathbf{a} + \beta\mathbf{b} + \gamma\mathbf{c},\] and \[2(\alpha + \beta + \gamma)\mathbf{s} = (\beta + \gamma)\mathbf{a} + (\gamma + \alpha)\mathbf{b} + (\alpha + \beta)\mathbf{c},\] where \[\alpha^{-1} = (\mathbf{a} - \mathbf{b})\cdot(\mathbf{a} - \mathbf{c}), \quad \beta^{-1} = (\mathbf{b} - \mathbf{c})\cdot(\mathbf{b} - \mathbf{a}), \quad \gamma^{-1} = (\mathbf{c} - \mathbf{a})\cdot(\mathbf{c} - \mathbf{b}).\] Verify that the centroid of the triangle divides \(SH\) in the ratio \(1:2\).

A convex polyhedron is such that precisely three faces concur in each vertex, and that every face is either a square or an equilateral triangle. Describe the possible cases.

5 points lie within a unit square, or on its boundary. Prove that some pair of them are at a distance apart less than or equal to \(\frac{1}{2}\sqrt{2}\), and that the smallest distance between pairs of points is only equal to \(\frac{1}{2}\sqrt{2}\) in one exceptional case.

Prove that, if \(0 < x < 1\), \[\pi < \frac{\sin\pi x}{x(1-x)} \leq 4.\]

Suppose, if possible, that \(\pi^2 = a/b\), where \(a\) and \(b\) are positive integers. Let \[f(x) = \frac{x^n(1-x)^n}{n!},\] \[G(x) = b\pi \sum_{r=0}^{n} (-1)^r\pi^{2n-2r}f^{(2r)}(x),\] where \(f^{(2r)}(x)\) denotes the \((2r)\)th derivative of \(f(x)\), and \(n\) is a positive integer. Prove that \[\frac{d}{dx}\{G'(x)\sin\pi x - \pi G(x)\cos\pi x\} = \pi^2 a^n \sin\pi x \cdot f(x),\] and deduce that \[\pi\int_0^1 a^n\sin\pi x \cdot f(x)dx = G(0) + G(1).\] Prove that the right-hand side of this equation is an integer. Show also that, by choice of \(n\) sufficiently large, the left-hand side can be made to lie strictly between 0 and 1. Establish a contradiction to the original supposition that \(\pi^2\) is rational.

\(X\) and \(Y\) are discrete valued random variables, and \[\text{Pr}(X = x, Y = y) = p(x, y), \quad \text{say}.\] The expectation of \(X\) conditional on the value of \(Y\) being \(y\) is defined as \(\mu(y)\), where \[\mu(y) = E(X|Y = y) = \sum_x x \frac{p(x, y)}{b(y)},\] and \[b(y) = \text{Pr}(Y = y),\] so that \[b(y) = \sum_x p(x, y).\] Show that \(E(X) = \sum\mu(y)b(y)\). By taking \(Z = X^2\), find an expression for the variance of \(X\) in terms of \(E(X|Y = y)\) and \(E(X^2|Y = y)\). An ornithologist observes that the number of eggs laid by a sparrow in a nest is distributed approximately as a Poisson random variable with mean \(\lambda\). He suspects that any egg has the same probability \(p\) of hatching, and that they are independent with respect to hatching. Denote by \(X\) the number of fledgelings from a nest, and denote by \(Y\) the number of eggs laid in that nest. Find expressions for \[E(X|Y = y) \quad \text{and} \quad E(X^2|Y = y)\] and hence find the (unconditional) mean and variance of \(X\). A second ornithologist contests that the eggs in a nest are not independent with respect to hatching. He suspects that either, with probability \(\pi\), the whole clutch of eggs hatches, or, with the probability \(1-\pi\), none of the clutch hatches. What are the mean and variance of \(X\) with this model? If you looked at a large sample of sparrows' nests, and found that the mean number of fledgelings per nest was 4, and the sample variance was 12, which ornithologist would you take to be more expert?