# Questions tagged [gray-codes]

A Gray code is a cyclic ordering of binary strings so that two successive values differ in only one bit (a Hamming distance of 1).

10 questions
Filter by
Sorted by
Tagged with
60 views

### Runs of identical bits from the runs of zeros

Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$. Let $wt(n)$ be A000120, number of ...
69 views

### Counting matchings in middle levels of the Boolean lattice

Let $k$ be a nonnegative integer and consider $C_k$, the set of all subsets $A$ of size $k$ in $[2k+1]=\{1,2,\ldots,2k+1\}$ as well as $C_{k+1}$, the set of all subsets $B$ of size $k+1$ in $[2k+1]$. ...
2k views

### "Gray code" for building teams

Motivation. In a team of $n$ people, we had the task to build subteams of a fixed size $k<n$ such that every day, $1$ person of the subteam is replaced by another person in the team, but not in the ...
95 views

### Balanced Gray codes for powers of 2

All of the binary 4-bit cyclic balanced Gray code sequences can be formed from simple reversals, bit-permutations, and circular shifts of the one Wikipedia example: ...
194 views

### Maximal distance of $2d+1$ points on a sphere

If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ as the vertices of the regular octahedron, then one can achieve a minimal spherical distance of $\pi/2$ between any two ...
290 views

### Are Gray codes in $\{0,1\}^n$ isomorphic?

Let $n\in\mathbb{N}$ be a positive integer. Two elements of $\{0,1\}^n$ form an edge if and only if their Hamming distance equals $1$. It is known that $\{0,1\}^n$ endowed with this graph structure ...
643 views

### New Perfect 2-bit Error Correction Code - Are there any other?

I have recently looked through perfect error correcting codes and found the Hamming(7,3) and Golay(23,7). Using a computer program I have found a new 2 bit perfect error correcting code: Code(90, 2). ...
1 vote
95 views

### Hamiltonian Path through $n$-bit strings with maximum number of $0\mapsto 1$ transitions

Let $G_n$ be the complete graph whose vertices are the $2^n$ $n$-bit strings. Let $H_n$ denote the Hamiltonian path through $G_n$ that uses the maximum number of edges that correspond to a single bit ...
1 vote
### How many non-overlapping k-hop neighborhoods can be uniquely colored on an $N$-dimensional hypercube?
Imagine I have a $N$-dimensional hypercube. My aim is to distinctly color as many non-overlapping $k$-hop neighborhoods as possible (i.e. sets of vertices connected by a Manhattan distance of at most ...