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.

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.