  Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of
length n whose plain complexity C(x) has almost maximal conditional complexity
relative to x, i.e., C(C(x)|x) > log n - log^(2) n - O(1). (Here log^(2) i =
log log i.) Following Elena Kalinina (Kalinina 2011), we provide a simple
game-based proof of this result; modifying her argument, we get a better (and
tight) bound log n - O(1). We also show the same bound for prefix-free
complexity.
  Robert Solovay showed (Solovay 1975) that infinitely many strings x have
maximal plain complexity but not maximal prefix complexity (among the strings
of the same length): for some c there exist infinitely many x such that |x| -
C(x) < c and |x| + K(|x|) - K(x) > log^(2) |x| - c log^(3) |x|. In fact, the
results of Solovay and Gacs are closely related. Using the result above, we
provide a short proof for Solovay's result. We also generalize it by showing
that for some c and for all n there are strings x of length n with n - C (x) <
c and n + K(n) - K(x) > K(K(n)|n) - 3 K(K(K(n)|n)|n) - c. We also prove a close
upper bound K(K(n)|n) + O(1).
  Finally, we provide a direct game proof for Joseph Miller's generalization
(Miller 2006) of the same Solovay's theorem: if a co-enumerable set (a set with
c.e. complement) contains for every length a string of this length, then it
contains infinitely many strings x such that |x| + K(|x|) - K(x) > log^(2) |x|
+ O(log^(3) |x|).
