Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics III / 9 / c / Solution

Sort the distinct observations as $x_{(1)}<\cdots <x_{(n)}$. For ordered centres $m_1<\cdots <m_r$, a point is closer to $m_j$ than to $m_{j+1}$ precisely when it lies to the left of their midpoint. Thus each Voronoi cell is an interval, with either choice allowed for an endpoint tie. Consequently, after assignment, each nonempty cluster is a contiguous block of the sorted observations.

The arithmetic means of disjoint ordered blocks are strictly ordered, so updating centres preserves this order. The empty-cluster repair in part (b) preserves contiguous blocks too: an observation farthest from its assigned centre lies at an endpoint of its block, and removing that endpoint makes a new singleton block. In one dimension with distinct observations, choosing $K$ distinct observations as initial centres makes the first assignment nonempty.

The one-dimensional K-means iteration bound now follows by counting block partitions. Choosing the $K-1$ gaps between consecutive nonempty blocks givespossibilities. By the strict-decrease argument in part (b), no such partition can recur before algorithm termination. Counting a step as an assignment, any empty-cluster repairs, and a centre update, with the stability check performed after that update, givesFor $K=1$, one update to the overall arithmetic mean suffices. Arbitrary changes between tied centres would invalidate the strict-decrease argument, which is why the stable tie convention in part (b) matters.