Let $\calA$ be any behavioral online algorithm for the $k$-cache problem. Thm: the competitiveness of $\calA$ against the adaptive online adversary is at least $k$. Proof: We define $k$ deterministic adversaries, named $\adv_1$, ... $\adv_k$. These adversaries will all make the same request at each step, but will maintain their own caches differently. There will be only k+1 pages altogether, which we call $x_0, x_1, ... x_k$. Assume the initial cache consists of pages $x_1, ... x_k$. Let $S^t$ be $\calA$'s cache after $t$ steps. For each $i$, let $A^t$ be $\adv_i$'s cache after $t$ steps. Each of the adversaries requests the same request sequence $\varrho = r^1 ... r^n$. The loop invariant that we maintain is: For each $t > 0$, $S^{t-1}$, $A^t_1$, ... $A^t_k$ are all different. Note: since there are $k+1$ pages altogether, and each of those sets has $k$ pages, each page is missing from exactly one of those sets. Note also that the intersection $A^t_1\cap A^t_1 \cap ... A^t_k$ consists of just one page, namely the one page that is missing from $S^{t-1}$. Furthermore, that page is $r^t$. We now describe the actions of the adveraries. The first step: $r^1 = x_0$. For each $i$, $\adv_i$ ejects $x_i$ and moves $x_0$ into its cache. Therefore, $\calA$ pays 1, and each $\adv_i$ pays 1. Each subsequent step: For each $t > 1$, let $r^t$ be the one page that is not in $S^{t-1}$. Therefore, $\calA$ faults and pays 1. There will be just one $i$ such that $A^{t-1}_i = S^{t-1}$. $\adv_i$ ejects $r^{t-1}$ and replaces it with $r^t$. Thus, $\adv_i$ faults and pays 1, while all the other adversaries pay 0.