TIFR2017-B-8

Question

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

Comments

Official Ans - Option A.

http://univ.tifr.res.in/gs2017/Files/GS2017_QP_CSS.pdf

---

The number of Gray codes possible will always be even. Hence, option A is correct. When n = 1, possible gray codes =2. When n =2, number of gray codes =4 and so on.

---

@smsubham

That was a mistake, read the answer again and the "PS" part.

---

Can't we consider like, for n = 1, we can have two orders like:

(0, 1) and (1, 0) ?

It seems correct though.

Answer 1

1. In the question it is stated that -> Thus, for $n=3$, the ordering $(000, 100, 101, 111, 110, 010, 011, 001)$ is a Gray code.
2. We have to find orderings such that they start with $0^{n}$, must contain all bit strings of length n and successive strings must differ in one bit. 

Options c and d are clearly wrong. 
Now, consider $n=1$. The only Gray code possible is $\left \{ 0,1 \right \}$. Hence no of Gray code $=$ odd for $n=1$.
For $n=2$ only two Gray code exists $\left \{ 00, 10, 11, 01 \right \}$ and $\left \{ 00, 01, 11, 10 \right \}$. Thus no of Gray code $=$ even for $n=2.$
Thus it is not that gray codes could be only even or only odd.
Hence, option e is correct.

PS: Official answer given was A - probably a mistake

Comments

I think option A is correct.

It says that "the number of possible Gray codes is even" or the number of gray codes possible from n bits. It doesn't say anything about the particular gray code that it is odd or even.

Please clarify

---

The number of Gray codes possible will always be even. Hence, option A is correct. When n = 1, possible gray codes =2. When n =2, number of gray codes =4 and so on.

---

nbnb

FOR N=2 (00 &11) ARE TO BE DISCARED 

---

set2018

why is that? 00,01,11,10 make gray code. Why would you discard 00 and 11? In the question, they have included 000&111 for N=3.

---

line in question "the ordering (000, 100, 101, 111, 110, 010, 011, 001) is a Gray code"

says that whole order is gray code and not just single string is gray code.

even though official answer is A , it can be incorrect

I think above answer is perfect

---

How many such orders are possible for an n-bit number?

---

@nbnb

No, that is not true.

C and D are false because in 000,001,011,010000,001,011,010 we have only one bit different for two strings separated by 22 strings. 

---

@techbd123

@shreyas

Do you both think this is a perfect answer or further explanation can be given?

 

---

@techbd123

@shreyas

Do you both think this is a perfect answer or further explanation can be given?

I wanted to correct every option.

 

Answer 2

option A is correct!

when n=1 possible gray codes={0,1}=2^1=2

when n=2 possible gray codes={00,01,11,10}=2^2=4

when n=3 possible gray codes={000,001,011,010,110,111,101,100}=2^3=8

and so on ; hence always even.

Comments

How is the total number of gray codes 2^n ? Could you please elaborate on it?

Answer 3

Option A and B says about number of possible gray codes of length n.

"A gray code is  a ordering of all n length binary strings starting with 0^n and successive n length strings will differ by one bit and first and last string also will differ by one bit".

So let's see how many possible gray codes can be found when n=1,2

when n=1 there is only one possibility {0 , 1}

when n=2 there is two possibilities {00,01,11,10} , {00,10,11,01}. It is because the gray code must start with 0^n and we can only have 01 or 10 after 00, and that is why we got two possibilities.

So from above observation we can clearly reject Option A and B because number of possible gray code for a given 'n' can be odd(in case of n= 1 it is 1) and also can be even(in case of n= 2 it is 2).

So A and B can not be our option

Now lets check for Option C and D

Lets take a possible gray code for n = 3 

 {000, 100, 101, 111, 110, 010, 011, 001}

Here 000 and 110 are separated by 3 strings (100,101,111) but they differ by 2 bits So That makes option C and D false.

So from above observations it is clear that Option E is the right choice.

 

Answer 4

Official answer (option A) is correct.

Number of Gray Codes will always be even. Gray Code is an ordering of codewords.

For eg., in the question, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is a Gray code. 000, 100 and all the other elements of this ordered set are codewords.

For n = 1, we have 2 Gray Codes. {0, 1} and {1, 0}.

For n = 2, we have 8 Gray Codes. {00, 01}, {01, 00}, {00, 10}, {10, 00}, {11, 01}, {01, 11}, {11, 10} and {10, 11}.

Observations :
1. There are $2^{n}$ codewords in every Gray Code of n bits..
2. For a given Gray Code, its reverse will also be a Gray Code.
3. Reverse of a Gray Code will always be distinct from the original Gray Code, as all elements are distinct.

Hence, number of all possible Gray Codes over n bits will always be even. (Don't confuse this with number of codewords in every Gray Code over n bits, although that will also be even and equal to $2^{n}$.)