> Please give me a hint on Problem 2.


Let $\calP$ be any metrical task system, and let $C$ be the competitiveness
of $\calP$.  Suppose that $\calA$
 is a barely random online algorithm for $\calP$,
\ie, a distribution among finitely many deterministic online
algorithms, $\calA_1\ldots \calA_n$.
Let $C_\calA$ be the competitiveness of $\calA$.
Prove that $C_\calA \ge \frac{C+n-1}{n}$.


First of all, $C$ is the deterministic competitiveness.    The default
adjective is "deterministic."  And, if I had meant randomized
competitiveness, the problem would be pointless.

Here is an example where this result plays.  Look at paging with k=2.
The competitiveness is known to be 2.  The randomized algorithm MIXED2
is barely random and is a distribution among 2 deterministic algorithms,
LRU and MRUS2.  According to the statement of Problem 2, since n=2, the
competitiveness of MIXED2 cannot be less than 1.5, which is exactly
what it is.
