Theorem: If M is a metric space with k+1 points, there is no deterministic algorithm for the k-server problem on M whose competitiveness is less than k. Proof: Let the points of M be x_0, x_1, ... x_k. We can assume that the servers start on x_1, ... x_k. Let A be an arbitrary deterministic online algorithm. We define k different deterministic offline algorithms, which we call B_1, ... B_k. The idea of the proof is that A's cost is equal to the sum of the costs of the B_i, except for a constant. Initially, each B_i has its servers on all points except x_0. At each step, the request is to the one point where A does not have a server. Let r^1, r^2, ... r^n be the request sequence; r^1 = x_0. Note that A serves the request at step t by moving a server from r^t+1 to r^t. The loop invariant is that each point other than the last request point is covered by all but one of the B_i. The loop invariant holds after each step. The initial request is to x_0. Each B_i serves that request by moving a server from x_i to x_0. The loop invariant is thus established. At step t, for t > 0, there is just one of the B_i that does not have a server at r^t. That B_i then moves its server from r^t-1 to r^t to serve the request. Note that, for all but the initial step, the cost for A is exactly the total cost of all k of the B_i. Thus, the average B_i has cost 1/k times the cost of A plus the initial cost. It follows that at least one of the B_i has cost at most 1/k times the cost of A plus a constant.