[35] It is easy to see that for every string x and every integer n, there is a y such that the information distance max{C(x|y), C(y|x)}

between x and y is n + O(1). Prove that for every n and for every string x such that C(x) ≥ 2n + O(1) there exists a string y such that both C(x|y) and C(y|x) are equal to n + O(1).

Comments. If the additive term O(1) were replaced by O(log n), then this exercise becomes straightforward. Source: [M.V. Vyugin, Theoret.

Comput. Sci., 271(2002), 145–150].