Proof that a string can't occur in more than one column of the standard array

First note that adding a string to itself will always give you the string consisting only of 0s, for which we write $\overline{0}$. That's because for each digit you either add 0 to 0 or 1 to 1. For example, 11000 + 11000 = 00000. Also, adding the zero string to any other string clearly leaves that string unchanged, e.g. 11000 + 00000 = 11000. Now suppose a string occurs in more than one column. This means that there are two code words, call them $c_1$ and $c_2$, and two other strings that occur in the first column, call them $a_1$ and $a_1$, so that $$c_1+a_1=c_2+a_2.$$

...	...	c1	...	c2	...
...	...	...	...	...	...
a1	...	c1+a1	...	...	...
...	...	...	...	...	...
a2	...	...	...	c2+a2	...

Adding $a_1$ to each side of the equation above gives $$c_1+a_1+a_1=c_2+a_2+a_1,$$ which simplifies to $$c_1=c_2+a_2+a_1.$$ Adding $c_2$ to each side gives $$c_1+c_2=c_2+a_2+a_1+c_2,$$ which simplifies to $$c_1+c_2=c_2+c_2+a_2+a_1=a_2+a_1.$$ Since we are dealing with a linear code, we know that the sum of two code words is itself a code word. This means that $c_1+c_2$, and therefore $a_2+a_1$, is a code word and therefore appears somewhere in the first row of the array.

...	...	c1	...	c2	...	a2+a1	...
...	...	...	...	...	...	...	...
a1	...	c1+a1	...	...	...	...	...
...	...	...	...	...	...	...	...
a2	...	...	...	c2+a2	...	...	...

Now suppose that out of $a_1$ and $a_2$, the string $a_1$ appears first in the array. The entry defined by the row corresponding to $a_1$ and the column corresponding to the code word $a_2+a_1$ is $$a_2+a_1+a_1=a_2.$$

...	...	c1	...	c2	...	a2+a1	...
...	...	...	...	...	...	...	...
a1	...	c1+a1	...	...	...	a2	...
...	...	...	...	...	...	...	...
a2	...	...	...	c2+a2	...	...	...

In other words, string $a_2$ occurs in the row corresponding to $a_1$, as well as further down as an entry in the first column. This is a contradiction, as we would not have chosen $a_2$ as an entry of the first column if it had already occurred further up the table. Therefore, the string $c_1+a_1=c_2+a_2$ only occurs once in the table.

Back to the main article

---

Code 2 has the same chance of success as code 1

Code 1 consists of code words of length two. The probability of transmitting one code word correctly is $$(1-p{)}^2.$$ For code 2 the probability of decoding a single code word correctly is $$(1-p{)}^3+p(1-p{)}^2.$$ This can be rewritten as $$(1-p{)}^3+p(1-p{)}^2=(1-p{)}^2(1-p+p)=(1-p{)}^2,$$ which is the same as for code 1. Since for both codes two code words need to be transmitted correctly, the probability of reaching the treasure is, in both cases, $$1-((1-p{)}^2{)}^2=(1-p{)}^4.$$

Back to the main article