Proof

Showing 51-52 of 52 problems
1988 Paper 1 Q4
D: 1500.0 B: 1516.0

Each of \(m\) distinct points on the positive \(y\)-axis is joined by a line segment to each of \(n\) distinct points on the positive \(x\)-axis. Except at the endpoints, no three of these segments meet in a single point. Derive formulae for \begin{questionparts} \item the number of such line segments; \item the number of points of intersections of the segments, ignoring intersections at the endpoints of the segments. \end{questionpart} If \(m=n\geqslant3,\) and the two segments with the greatest number of points of intersection, and the two segments with the least number of points of intersection, are excluded, prove that the average number of points of intersection per segment on the remaining segments is \[ \frac{n^{3}-7n+2}{4(n+2)}\,. \]

Show Solution
  1. There are \(m \cdot n\) line segments, since each of the \(m\) points on the \(y\)-axis correspond to \(n\) points of the \(x\)-axis.
  2. Every pair of points on the \(x\)-axis and pair of points on the \(y\) axis will generate \(4\) lines, but only \(1\) of those points will meet in the middle, therefore there will be \(\binom{m}{2} \binom{n}{2}\) intersections.
The segment joining the smallest \(x\) to the smallest \(y\) and the segment joining the largest \(x\) to the largest \(y\) will not meet any other segments. The segment joining the smallest \(x\) to the largest \(y\) and the segment joining the largest \(x\) to the smallest \(y\) will have the largest number of intersections. They each intersect all the other segment coming out of other points (except the ones headed for the same point) ie \((m-1)(n-1)\) each. They also intersect each other, so \(2(m-1)(n-1)-1\) points. Therefore we are interested in: \begin{align*} \frac{\binom{n}{2}\binom{n}{2} - 2(n-1)^2+1}{n^2-4} &= \frac{\frac{n^2(n-1)^2}{4} - 2n^2+4n-1}{n^2-4} \\ &= \frac{n^4-2n^3+n^2-8n^2+16n-4}{4(n^2-4)} \\ &= \frac{(n - 2) (n^3 - 7 n + 2)}{4(n^2-4)} \\ &= \frac{n^3-7n+3}{4(n+2)} \end{align*}
1987 Paper 3 Q1
D: 1500.0 B: 1500.0

Find the set of positive integers \(n\) for which \(n\) does not divide \((n-1)!.\) Justify your answer. [Note that small values of \(n\) may require special consideration.]

Show Solution
Claim: \(n \not \mid (n-1)!\) if and only if \(n\) is prime or \(4\) Proof: \((\Leftarrow)\)
  1. \(4 \not \mid 3! = 6\).
  2. If \(p\) is prime, then \(p \not \mid k\) for \(k < n\), therefore \(p \not \mid (n-1)!\)
\((\Rightarrow)\) If \(n = 1\) then \(1 \mid 0! = 1\) so \(1\) is not in our set. The numbers less than \(6\) are all accounted for (either primes, \(4\) or \(1\)), so let \(n\) be a composite number larger than \(6\), ie \(n = ab\). Suppose first \(a \neq b\) then \((n-1) = 1 \cdots a \cdots b \cdots (n-1)\) so \(n \mid (n-1)!\). Suppose instead that \(a = b\), then \(n = a^2\). Since we know \(a \geq 3\) we must have \(1 \cdots a \cdots (2a) \cdots (a^2-1)\) so \(a^2 \mid (n-1)!\) and we're done.