jasperE3 wrote: Sunny wants to send some secret message to usjl. The secret message is a three digit number, where each digit is one digit from $0$ to $9$ (so $000$ is also possibly the secret message). However, when Sunny sends the message to usjl, at most one digit might be altered. Therefore, Sunny decides to send usjl a longer message so that usjl can decipher the message to get the original secret message Sunny wants to send. Sunny and usjl can communicate the strategy beforehand. Show that sending a $4$-digit message does not suffice. Also show that sending a $6$-digit message suffices. If it is deduced that sending a $c$-digit message suffices for some $c>6$, then partial credits may be awarded. Isn't this similar to hamming error correction?

(a) Let $A$ be the set of three-digit numbers, $B$ be the set of four-digit numbers. We connect two elements in $B$ if and only if they are different in exactly one digit. Sunny's encryption can be written as a function $f:A \to B$. For $a \in A$, let $C(a)=\{ f(a) \} \cup N(f(a))$ to be the possible cipher of $f(a)$ after altering. For any $x,y \in A$, we must have $C(x) \cap C(y) = \emptyset$, otherwise usjl cannot distinguish $x$ and $y$. Therefore $10^4=|B| \ge | \cup_{a \in A} C(a)|=\sum_{a \in A} |C(a)|=37 \cdot 10^3$, which is absurd. (b) The algorithm is mapping $(a,b,c)$ to $(a,b,c,a+b,b+c,c+a)$ (all digits are modulo $10$). Usjl first checks if three equality of $a+b,b+c,c+a$ is correct. (i) If no digits are altered, then all three equality is correct. (ii) If one digit in $\{ a,b,c \}$ is altered, WLOG $a$, then only $b+c$ is correct. (iii) If one digit in $\{ a+b,b+c,c+a \}$ is altered, WLOG $b+c$, then only $a+b$,$c+a$ is correct. Hence usjl is possible to distinguish from (i) (ii) and (iii). If (i) or (iii) happens, then $a,b,c$ are correct, we win. If (ii) happens, WLOG $b+c$ is correct, then $b,c$ are correct. Usjl also knows the correct value of $a+b$, so he can compute the correct value of $a$.