Theorem 2. There is no online deterministic algorithm for the cache problem of competitiveness less than k, where k is the cache size. Suppose that A is a deterministic online algorithm for the cache problem. We will design a request sequence such that A pays at least k times the cost of the optimal offline algorithm. This request sequence will utilize only k+1 distinct pages. Let P be a set of k+1 pages, such that the initial cache is a subset of P. At each step, let the request be to the one member of P which is not in A's cache. Thus, A faults at every step. Call this request sequence rho. (rho is called the "cruel" request sequence.) We partition rho into "phases" as follows. The first phase begins with the first request. Phases are as long as possible, subject to the rule that no phase contains all members of P. If a phase cannot be continued, a new phase begins. (For example, suppose k = 4, and rho = ebecbdeabcedaebecdabecdadabeb. Then the partitioning of rho into phases is: ebecbde|abce|daebe|cdab|ecdada|beb.) Claim 1: Each phase (except perhaps for the last one) has length at least k. Proof: A new phase cannot begin until k distinct pages have been requested on the old phase. Claim 2: Opt faults at most once during each phase. Proof: At the beginning of each phase, Opt ejects a page that will not be requested during that phase. (There is always just one such page, except possibly for the last phase.) Opt will then have no further faults during that phase. We now finish the proof of Theorem 2. Let N be the length of rho, and let M be the number of phases. Then A pays N. By Claim 2, Opt pays at most M. By Claim 1, N >= (M-1)k+1. The ratio N/M is thus bounded below by k, as N grows without bound.