Lesson 2

It is clear that at least \(2^{n}-1\) switches are needed: if we make fewer, we cannot guarantee that we will try all combinations. Below we show that \(2^{n}-1\) switches are sufficient. For this, we will show how to enumerate all binary strings of length \(n\) in such an order that any two adjacent strings (as well as the first and last) differ in exactly one bit.

An order on binary strings of equal length, where any two adjacent strings differ in exactly one bit, is called a Gray code. Below we give one of its constructions.