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).

Filter by
Sorted by
Tagged with
5
votes
1answer
244 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 ...
2
votes
1answer
328 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
1answer
87 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
1answer
109 views

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 ...
3
votes
1answer
996 views

Sprague-Grundy sequence for the ruler game

Consider the game "Ruler", which is defined as follows. We start with finitely many coins in a line. A move in this game consists of turning over any number of coins, but they must be consecutive, ...