# How long message can I send?

I know the $n$-bit message ($M$).

I have to send it to the receiver bit by bit.

For each bit I can also send one bit of comment ($C$).

Before receiver gets the bit, he have to guess it($G$).

After all, $M$, $C$ and $G$ should differ only in $k$ places, ie: $$||(M \underline{\vee} C) \vee (M \underline{\vee} G)|| \leq k$$

Receiver and I both know the protocole of sending the message, so he can guess some informations basing on my comments.

What is the maximal length of the message I can send?

the only solution I've found is $n=2k$, which is pretty obvious (eg. in the first $k$ bits of $C$ I send the second half of the message). Is it possible to construct the protocole in the way, that it allow to send messages longer than $2k$?

• Do I understand correctly that the worst case of the "guess" has to satisfy the inequality? So in fact the receiver must be able to deduce a "guess" from the message and comment bits already received such that the inequality is satisfied? – joriki Sep 7 '18 at 14:32
• Yes. The receiver have to guess $i+1$st bit basing on the $i$ previous bits. – Jaroslaw Matlak Sep 7 '18 at 19:17
• No, that part was clear. My question was about whether you want a worst-case analysis. – joriki Sep 7 '18 at 19:26
• Also yes. I want to be sure, that the inequality is satisfied regardless the message $M$ – Jaroslaw Matlak Sep 7 '18 at 20:29