Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$
A paper of Day gives the following hint: Show that for every $c$, every long enough string $z$ contains a prefix $x$ with $K(x) &lt; |x| - c$.

He also gives a hint to the hint: Use the fact that a machine for computing $x$ can use both the given program $\pi$ and its length $|\pi|$, which gives it an extra $\log|\pi|$ bits of information.