0
$\begingroup$

For any natural number n, an ordering of all binary strings of length n is a Gray code if it starts with 0^n, and any successive strings in the ordering differ in exactly one bit (the first and last string must also differ by one bit). Thus, for n=3, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is a Gray code. Which of the following must be TRUE for all Gray codes over strings of length n ?

A. the number of possible Gray codes is even

B. the number of possible Gray codes is odd

C. In any Gray code, if two strings are separated by k other strings in the ordering, then they must differ in exactly k+1 bits

D. In any Gray code, if two strings are separated by k other strings in the ordering, then they must differ in exactly k bits

E. none of the above

==================================================================== My take-

Now, consider n=1. The only Gray code possible is {0,1}. Hence no of Gray code = odd for n=1.

For n=2 only two Gray code exists {00,10,11,01} and {00,01,11,10}. Thus no of Gray code = even for n=2.

So, what should be the answer? A or E.

Also, how to check option C and D?

Any help to understand this question is highly appreciated.

$\endgroup$
0
$\begingroup$

C and D are false because in $000, 001, 011, 010$ we have only one bit difference for two strings separated by $2$ strings. You already showed A and B wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.