= Solution
{c}
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 gives
$$
\binom{n-1}{K-1}\le n^{K-1}
$$
possibilities. 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, gives
$$
\boxed{\text{number of steps}\le\binom{n-1}{K-1}\le n^{K-1}.}
$$
For $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.
Back to article page
