2
$\begingroup$

Consider a chessboard with $(n_1 \times n_2)$ squares, where we would like to assign a unique binary string, of some length $L$, to each square s.t. the Hamming distance between the strings corresponding to two squares on the board, $(s_a,s_b$), exactly corresponds to the Manhattan distance $H$ between $s_a$ and $s_b$ CONDITIONAL upon having $H \leq C$, where $C \in \mathbb{Z}$ is some integer constant.

Knowing that $L \geq \frac{ln(n_1 \times n_2)}{ln(2)}$, what value for the minimum binary string length $L$ allows for this? And is there a clever way to perform the string assignment for each square? The problem becomes uninteresting for $C \approx max(n_1,n_2)$, but for small values of $C$, it seems like there could be a neat strategy to achieve small values for $L$ relative to what one might expect.

(I apologize. When I previously asked this question, I specified that we should consider Chebyshev instead of Manhattan distances, and this is of course impossible for $(n_1,n_2) >1$.)

$\endgroup$
5
  • 1
    $\begingroup$ It seems that a "benchmark" construction is to take strings of length $n_1+n_2-2$ and have, for $1\leq i <n_1$, a bit indicating whether the fist coordinate is strictly larger than $i$, and similarly for $1\leq j < n_2$ a bit indicating whether the second coordinate is larger than $j$. In other words for each horizontal and vertical line separating rows and columns of squares, there is a bit that flips exactly when you cross it. $\endgroup$ Mar 31 '14 at 5:14
  • $\begingroup$ If $C$ is infinite, this seems to be essentially the only possibility. So the question is whether we can decrease $L$ if $C$ is finite. For $C=1$ we could have taken $L=1$ and the black/white chessboard pattern, but for some reason you don't like to have the same bit-string on different squares, is that right? $\endgroup$ Mar 31 '14 at 5:28
  • $\begingroup$ @JohanWästlund Regarding not having the same bit pattern on different squares, right, I'd like all squares to have a unique bit string. It's what makes this question interesting to me actually. $\endgroup$
    – RHayden
    Mar 31 '14 at 6:06
  • $\begingroup$ You want to assign the same binary string to each square??? Or was "unique" a typo for "different"???? $\endgroup$
    – bof
    Apr 4 '14 at 8:14
  • $\begingroup$ @bof Is my english here incorrect? I thought "different unique binary string" would be implied? $\endgroup$
    – RHayden
    Apr 6 '14 at 7:26
1
$\begingroup$

Ignoring uniqueness, short answer is that for $\min(n_1, n_2) > C$ we need exactly $L = 2C$ bits.

When you want global uniquness, you can solve this with $L = \log_2 \left(\frac{n_1 n_2}{C^2}\right) + 2C$ bits. I can't claim it is optimal though.

But first, the non-unique case: As a starting point, I thought of a $1$-dimensional problem, where instead of a $n_1 \times n_2$ board you have a $n_1 \times 1$ board, i.e., a row.

$1$-D case: The problem will be to find a set of strings $\{S_0, S_1, S_2, ..., S_{n_1 - 1}\}$ such that for a given $C$ and any $i, j \ge 0$, $d_{H}(S_i, S_j) = |i - j|$ if $|i - j| \le C$ and an arbitrary value if $|i - j| > C$.

Let's start with $n_1 = C + 1$, and let $S_0, S_1, ..., S_C$ be such a sequence. Then, The sequence $S_0 \oplus S_0, S_0 \oplus S_1, ..., S_0 \oplus S_C$ is also such a sequence. As a result, we could look for the sequence with $S_0 = \mathbf{0}$, i.e., all zeros.

Lemma $1$: For $n_1 = C + 1$, $L^* = C$ and one optimal sequence is: $$ S_i = 0^{C-i}1^i $$ where $x^i = \underbrace{xx...x}_{i \text{ times}}$.

Proof: To get $d(S_{C}, S_0) = C$ we need at least $C$ bits. The sequence above has exactly $C$ bits.

Now lets consider the case $n_1 > C + 1$.

Lemma $2$: For $n_1 = 2C$, $L^* = C$ and the sequence below is one solution: $$ S'_i = \left\{ \begin{array}{cc} S_i & i\le C \\ \overline{S_{i - C}} & C < i < 2C \end{array} \right. $$ where $S_i$ is the same as the sequence in Lemma $1$ and $\overline{S_i}$ is the inverted string for $S_i$.

Proof: From Lemma $1$, $L^* \ge C$. The given construction achieves $L = C$. Therefore, $L^* = C$.

Lemma $3$ : For any $n_1 \ge C + 1$, $L^* = C$. Proof: By Lemma $1$, $L^* \ge C$. Consider the sequence $S''_i$ as follows: $$ S''_i = S'_{i \mod 2C}. $$ Then $S''_i$ is a solution and with $L = C$. Therefore, $L^* = C$.

Now we can construct a suboptimal strategy for the $2$-Dimensional case:

Lemma $4$ : For a $n \times n$ chessboard we have $L^* \le 2C$. Proof : Let $S(i, j)$ as the string in grid cell $(i, j)$. For two strings $X$ and $Y$, let $XY$ denote the concatenation of $X$ and $Y$. Now let $S_{i,j} = S''_iS''_j$. For any $(i, j)$ and $(k, l)$ we have

$$ d\left( S_{i, j}, S_{k, l}\right) = d\left( S''_i S''_j, S''_k S''_l \right) = d\left( S''_i, S''_k \right) + d\left(S''_j, S''_l\right) = |i - k| + |j - l|. $$ On the other hand for $S_{i,j}$ given above we have $L = 2C$. Therefore, $L^* \le L \le 2C$. The inequality $L^* \ge C$ comes from Lemma $1$.

Lemma $5$: For the chessboard with $n_1 = n_2 = C + 1$ we have $L^* = 2C$.

Proof : Let the length of a string be $L$ and $S_{0,0} = \mathbf{0}$. We must have: $$ d(S_0, S_{i,C-i}) = C, \; i \in {0, 1, 2, ..., C}. $$ Then each of the strings $S_{i, C-i}$ must have exactly $C$ ones and $L - C$ zeros. On the other hand, we must have $$ d(S_{i, C - i}, S_{0, C}) = 2i $$ Since the total number ones in both strings are the same, then we can only achieve this by flipping a one and a zero. For $C$ flips we need at least $C$ zeros in $S_{0, C}$ which suggests that $L^* \ge 2C$. This with Lemma $4$ proves that $L^* = 2C$.

As a corollary, for a general chessboard with $n_1 > C$ and $n_2 > C$ we find that $L^* = 2C$.

The Unique Strings Case Let's move back to Lemma $2$ and reconsider the sequence $S'_i$. Take prefix $X_k$ and consider the sequence below:

$$X_kS'_0, X_kS'_1,...X_kS'_{2C - 1}, X_{k + 1}S'_{2C - 1}, X_{k + 1}S'_0, ...$$

Let's assume that for all $k$, $d(X_{k}, X_{k + 1}) = 1$. Then the sequence above satisfies the Manhattan distance constraint. See that:

$$ \begin{array}{c} d(X_k S'_{2C - 1}, X_{k + 1} S'_{2C - 1}) = 1 \\ d(X_{k + 1}S'_{2C - 1}, X_{k + 1}S'_i) = i \\ d(X_{k}S'_{2c - i}, X_{k+1}S'_{j}) = 1 + d(S'_{2C - i}, S'_{j}) = 1 + |i - j| \end{array} $$ which are all valid in terms of their Manhattan distance.

$X_k$ could be any grey-coded sequence of length $n$ and hence, with length $n + 2C$, we can make $2^{n} \times (2C)$ strings. As a result, the length required for building $N$ strings is $\log_2\left( \frac{N}{C} \right) + C + 1$.

Note that for small $C$, this is asymptotically optimal. For $2D$ we can follow the same pattern as that of Lemma $4$ and $5$ and come up with $\log_2 \left( \frac{n_1n_2}{C^2} \right) + 2C$. Again for small $C$, I guess, the method gives a tight bound.

$\endgroup$
1
  • $\begingroup$ In the proof of Lemma 5, you seem to apply the condition to the points $S_{0,C}$ and $S_{C,0}$, whose Manhattan distance is $2C$. So it seems that this idea allows to provo only that $L\geq [3C/2]$... $\endgroup$ Sep 17 '16 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.