We can use the 2n different binary strings of length n to code (i.e., uniquely label) 2n distinct objects. However, some pairs of these 2n objects will have codes that differ only in one position. Thus, if we mistype even a single bit of an object's code we would inadvertently specify a different object than the one intended. For example, suppose n = 4 and the code for "Apple iPhone" is 0110 while the code for "Samsung Galaxy" is 0010. If we wanted to order the iPhone through a web form but mistyped the second bit of its code, we would receive the Galaxy instead! To avoid this, we would like the objects to be coded in such a way that no two of them have codes that differ in only one position. In that case, if we make only one typing error in entering the code, the system could inform us that the code we entered is invalid, instead of mistaking it for the code of a different object. Coding schemes that have this property are called "error-detecting codes".
The question now arises: Using binary strings of length n, how many different objects can we label in such a way that there are no two objects whose codes differ in only one position? In this question, you will show that the answer is 2n-1.
a. Let n be any positive integer, and let S be any set of binary strings of length n such that no two strings in S differ in only one position. Prove that S contains no more than 2n-1 strings.
b. Prove that for every positive integer n, there exists a set S of binary strings of length n that contains 2n-1strings no two of which differ in only one position. (There are multiple ways to prove this, not all of which involve induction. You need only give one proof, which may or may not use induction.)