Suppose we have an $n$-tuple of ternary values (0, 1, or 2). At most one of the elements will change its value. What is the least amount of information we need to remember in advance to correctly identify whether or not such a change has occurred and, if it has, what element has changed?
For $n=3$, I have found a way that needs just $\log_2(9)\approx3.17$ bits of information: remember the sum modulo 3 of the the first two elements, the same for the last two. For example, for "021" we store $2$ and $0$. If the first element gets changed to a 2 (making it "221"), then the new sums (mod 3) will be $1$ and $0$. As $2\neq1$ and $0=0$, we know that an element has changed and that it has to be the first one.
Is there a solution for n=3 that requires even less memorized information? Can we find this minimum in general for any natural $n$?
Update: We can proof that for $n=3$, $2$ trits are indeed optimal. If we divide all the different $3$-tuples into buckets with the same memorized information, no two tuples in a bucket can share an element at any position: if there were such tuples $xab$ and $xcd$, then both could be transformed to $xcb$ and we wouldn't be able to tell which element got changed (or if a change occurred). That means a bucket can hold at most $3$ different tuples. As there are $27$ total, the minimum number of buckets is $9$, which can be used as seen above. $\square$
It is more natural to use trits for this problem instead of bits. From now on, all addition and multiplication is modulo $3$.
It suffices to store $1+\lceil\log_3 n\rceil$ trits of information. Let $x_0,x_1,\dots,x_{n-1}$ be the data. Let $\ell=\lceil\log_3 n\rceil$, and let $y_0,y_1,\dots,y_\ell$ be information we store, each of which is in $\{0,1,2\}$. Specifically, \begin{align} y_0&\equiv x_0+x_1+x_2+\dots+x_{n-1} &\pmod3\\ y_1&\equiv x_1+2x_2+x_4+2x_5+\dots &\pmod 3\\ y_2&\equiv x_3+x_4+x_5+2x_6+2x_7+2x_8+x_{12}+\dots &\pmod 3\\ y_3&\equiv x_9+x_{10}+\dots+x_{17}+2x_{18}+\dots+2x_{26}+\dots &\pmod3\\ &\;\;\vdots \end{align}
In words, $y_0$ is simply the sum of the information trits. For each $k\in \{1,\dots,\ell\}$, $y_k$ is a linear combination of all of the data trits, where the coefficient of $x_j$ is the $k^{\text {th}}$ trit of $j$ when written in ternary.
How do we determine the changed data? Let $\hat y_k$ denote the result of the above formulas using the new data.
First, compute $\hat y_0-y_0\pmod 3$. If the difference is zero, there is no error. Otherwise, the difference tells you whether or not the error was $x\to x+1$ or $x\to x+2$. In what follows, I will write "$1\;(2)$" to mean "$1$ in the case where the change is $x\to x+1$, and $2$ in the case where the change is $x\to x+2$".
Assuming there was a change, look at $\hat y_1-y_1$.
If the difference is $0\;(0)$, you know the changed value is one of $x_0,x_3,x_6,\dots$
If the difference is $1\;(2)$, you know the changed value is one of $x_1,x_4,x_7,\dots$
If the difference is $2\;(1)$, you know the changed value is one of $x_2,x_5,x_8,\dots$
Next, look at $\hat y_2-y_2$.
If the difference is $0\;(0)$, you know the changed value is one of $x_0,x_1,x_2,x_9,x_{10},x_{11},\dots$
If the difference is $1\;(2)$, you know the changed value is one of $x_3,x_4,x_5,x_{12},x_{13},x_{14},\dots$
If the difference is $2\;(1)$, you know the changed value is one of $x_6,x_7,x_8,x_{15},x_{16},x_{17},\dots$
$\vdots$
And so on and so forth. In summary, the difference $\hat y_1-y_1$ tells you the least significant trit of the index of the changed data, $\hat y_2-y_2$ tells you the second least significant trit, and so on.
I know that my strategy is very close to optimal. You need to store at least $\log_3(n+1)$ trits of information, since you need to decide between $n+1$ options (either one of the $n$ data trits has changed, or none of them have). The difference between $1+\lceil \log_3 n\rceil$ and $\log_3(n+1)$ is always at most $2$.