EDIT: FOR SOME REASON the proof was showing up as a giant block of white and highlighting the text was the only way I could fix it. Sorry for the inconvenience.
The question says:
Binary strings are sequences of the two digits (or bits) 0 and 1. The two binary strings of length 1 (each having 1 character) are 0 and 1. These two strings can be arranged in a list so that each string on the list differs from its neighbours by exactly one bit:
- 0
- 1
I can arrange all four binary strings of length 2 in a list so that each string on the list differs from its immediate neighbours by exactly one bit, even if I insist that the first and last strings on the list are immediate neighbours:
- 00
- 01
- 11
- 10
Can you arrange all 2^n binary strings of length n in a list so that each string on the list differs from its immediate neighbours by exactly one bit, when you treat the first and last strings on the list as immediate neighbours?
----------------------------------------------------------
1. Understanding the problem
The question is basically asking if you can arrange a list of all the binary strings of some length such that the binary string before or after the string on the list differs only by 1 bit, AND if the first and last binary strings on the list differ by 1 bit.
2. Devising a plan
To prove that this sorted list of binary strings is possible, I will use Mathematical Induction to prove it. First, I will show that this list possible for a base case where the binary string length is 1. Then assuming that it holds for any length binary string n, I will show it is true in the n + 1 case. There have been many cases in class where we had to work with binary strings, but the problems were quite different than the one presented now.
Another way to think of the question is can you constantly change a binary string of length n by only 1 bit, and eventually create a list of all the binary strings of length n, and then rearrange them so that the first and last strings also differ by 1 bit?
3. Carrying out the plan
PROOF:
Define:
P(n) = All 2^n binary strings of length n in a list are arranged so that each string on the list differs from its immediate neighbours by exactly one bit, and the first and last strings on the list can be treated as immediate neighbours.
We must show that for all n belonging to the natural numbers, P(n) is true.
Base case: n = 1:
Then 2^1 = 2, so there are 2 possible binary strings of length 1. These strings are 0 and 1. Clearly these strings only differ by 1 bit, and they can be arranged such that each string's immediate neighbour differs by 1 bit. Since they are the only 2 strings in the list, then the first and last strings on the list can also be treated as immediate neighbours, and thus differ by 1 bit. Therefore P(1) holds.
Assume P(n) holds for all natural numbers n (IH). Then we must show that P(n + 1) holds.
We define L to be the list that contains 2^n binary strings of length n, and also assume the list satisfies P(n). Then, we define two other lists named L_0 and L_1.
The list L_0 will contain all of the binary strings in L with 0 prepended to each binary string in the list. Likewise, L_1 will contain all of the binary strings in L with 1 prepended to each binary string in the list. Thus, each list will contain 2^n binary strings of length n + 1. Each list will be arranged such that each string's immediate neighbours differ by 1 bit, and the first and last binary string in the list can be treated as immediate neighbours (this is true since prepending the same bit to all the strings that already differ by 1 bit will not change the number of bits it differs by). Then, if we take L_1 and flip it such that the first binary string is now the last binary string (and vice versa), we can add it to the bottom of L_0. This will give us a list of 2^n + 2^n = 2*2^n = 2^(n + 1) strings of length n + 1 such that each string's immediate neighbour differs by 1 bit. Now, the first and last binary string can be treated as immediate neighbours since we flipped L_1 before appending it to L_0.
The flip allows the first and last binary string to be treated as immediate neighbours since the first binary string in L_0 is the first binary string in L prepended with 0, and the first binary string in L_1 is the first binary string in L prepended with 1; this means those binary strings only differ by 1 bit since the rest of the string is the same. The same applies to the last binary strings in L_0 and L_1; the binary strings only differ by 1 bit since it was just the same string prepended with a different bit. By flipping L_1, the first binary string (which only differed by 1 bit to the first binary string in L_0), became the final string and therefore satisfies the condition in P(n) for the first and last binary strings to be considered immediate neighbours. Also, since the last binary string in L_1 (which only differed by 1 bit to the last binary string in L_0) became the first string, it satisfies the condition that the immediate neighbours only differ by 1 bit inside the list. Since these two "border cases" of each list come together and satisfy P(n), and since the rest of the list also satisfies P(n) (by IH), then therefore P(n + 1) holds.
Therefore, since P(n + 1) holds, P(n) holds.
Therefore, for all n belonging to the natural numbers, P(n) holds. QED
4. Looking back
The proof seems solid, since we take care of all the possible cases of n via Mathematical Induction. This result can most likely be not used for other problems. For instance, if we were to use alphabetical strings, then we can apply the same idea where each string will differ by one letter. However, there are many more types of letters than types of bits, then the first and last strings would also differ by many more letters. Whether there are more ways for this proof to be applied to other problems is something that would need to be looked into more.
