Mixing
Gray codes over strings of length n?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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.
gray-code
asked Jul 15 at 11:58
Geeklovenerds
11
add a comment |Â
up vote
0
down vote
favorite
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.
gray-code
asked Jul 15 at 11:58
Geeklovenerds
11
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jul 15 at 12:07
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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.
gray-code
asked Jul 15 at 11:58
Geeklovenerds
11
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.
gray-code
asked Jul 15 at 11:58
Geeklovenerds
11
asked Jul 15 at 11:58
Geeklovenerds
11
asked Jul 15 at 11:58
Geeklovenerds
11
asked Jul 15 at 11:58
Geeklovenerds
11
11
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jul 15 at 12:07
add a comment |Â
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jul 15 at 12:07
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jul 15 at 12:07
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jul 15 at 12:07
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
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.
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
add a comment |Â
up vote
0
down vote
We need to find the order which starts with $0^n$ which also need to have all the bit strings of length $n$ $($Here $n=3$$)$ and successive strings differ $1$ bit. Therefore, we can eliminate options $C$ and $D$.
The number of Gray codes possible will always be even. So, option $A$ is correct.
answered Jul 15 at 12:06
Key Flex
4,406525
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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.
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
add a comment |Â
up vote
0
down vote
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.
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
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.
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
answered Jul 15 at 12:06
Hagen von Eitzen
265k20258477
265k20258477
add a comment |Â
add a comment |Â
up vote
0
down vote
We need to find the order which starts with $0^n$ which also need to have all the bit strings of length $n$ $($Here $n=3$$)$ and successive strings differ $1$ bit. Therefore, we can eliminate options $C$ and $D$.
The number of Gray codes possible will always be even. So, option $A$ is correct.
answered Jul 15 at 12:06
Key Flex
4,406525
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
add a comment |Â
up vote
0
down vote
We need to find the order which starts with $0^n$ which also need to have all the bit strings of length $n$ $($Here $n=3$$)$ and successive strings differ $1$ bit. Therefore, we can eliminate options $C$ and $D$.
The number of Gray codes possible will always be even. So, option $A$ is correct.
answered Jul 15 at 12:06
Key Flex
4,406525
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We need to find the order which starts with $0^n$ which also need to have all the bit strings of length $n$ $($Here $n=3$$)$ and successive strings differ $1$ bit. Therefore, we can eliminate options $C$ and $D$.
The number of Gray codes possible will always be even. So, option $A$ is correct.
answered Jul 15 at 12:06
Key Flex
4,406525
We need to find the order which starts with $0^n$ which also need to have all the bit strings of length $n$ $($Here $n=3$$)$ and successive strings differ $1$ bit. Therefore, we can eliminate options $C$ and $D$.
The number of Gray codes possible will always be even. So, option $A$ is correct.
answered Jul 15 at 12:06
Key Flex
4,406525
answered Jul 15 at 12:06
Key Flex
4,406525
answered Jul 15 at 12:06
Key Flex
4,406525
answered Jul 15 at 12:06
Key Flex
4,406525
4,406525
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
add a comment |Â
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
@Hagen von Eitzen@Key Flex So, with which option should I go? A or E
– Geeklovenerds
Jul 15 at 12:13
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
Most probably $A$ because the number of gray codes possible will be even.
– Key Flex
Jul 15 at 12:16
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852455%2fgray-codes-over-strings-of-length-n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
– José Carlos Santos
Jul 15 at 12:07