Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$ I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here looking for a hint. I don't want a full answer, but would really appreciate a few words to point me in the right direction. This is not a homework exercise.
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.