35 views

Was solving the GO 2019 pdf when I encountered this question asked in TIFR 2017. Although I have understood this question, I have one doubt-

It is mentioned in the question that for a 3-bit number, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is one of the possible Gray codes.

Then, how many such orders are there for an n-bit number?

0

it sounds correct.

In this problem we have 2 constraints,

1. each consecutive representation should differ by 1 bit only.
2. all the circular rotations possible for a sequence of representations is counted as 1.

therefore here we have to find the number of circular permutations of grey codes possible using n-bit.

here the solution would be to generate a recurrence relation and then solve it to get the answer.

0

I further tried to reduce this to a graph theory problem-

I considered the cells as nodes drew an edge between the nodes if they were adjacent (i.e. differed by 1 bit). Then the problem basically reduced to finding the no. of cycles from the node representing cell (0,0) (say, the origin) that pass through each vertex exactly once, i.e. finding the no. of distinct directed Hamiltonian cycles.

Am I correct in proceeding as such? Further, is there any formula to find the no. of distinct directed Hamiltonian cycles for any arbitrary graph?

0

It will look like this and we have to find hamiltonian cycles possible right ?

assume $\rightarrow$ is bidirectional

0
I don't think there should be an edge between node(01) and node (10) as they differ by 2 bits.
0

like this right ?

0
Yes, this one is correct.
0
So, if I am not mistaken, the problem reduces to finding the no. of distinct directed Hamiltonian cycles for such a graph where nodes (that represent the Gray codes) have an edge between them only if they differ by 1-bit position.
0
Yes just 1 mistake

we have to find hamiltonian paths and not hamiltonian cycles

In the above graph there is only 1 cycle possible starting from 00 i.e. 00-01-11-10-00 and all other cycles are just its rotation.

but there are 2 hamiltonian paths starting from 00 i.e. 00-01-11-10 or 00-10-11-01
0
every time the hamiltonian paths will be different right , there is not any general formula ?

we can't generalize it as it will vary from graph to graph

$\therefore$ we have to do it by brute force technique if we are using graph method.
+1
Yeah, you are right. Here, we are trying to find the no. of Hamiltonian paths and not Hamiltonian cycles. Also, such graphs are actually a special type of graphs called Hypercubes (somehow I completely forgot about them 😅). Also, finding the no. of Hamiltonian paths in an arbitrary graph is an np-complete problem. So, no other option apart from brute-force.

1
2