5
$\begingroup$

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (consisted of not necessarily consecutive bits). Now we have to find the maximum number from the numbers in S so that every pair of numbers is "compatible" and I want an example numbers from S with that maximum. Here is an example of the task:

n = 6; S = { 000000, 000001, 000010, 000011, ..., 111110, 111111 }; The maximum number from the numbers in S with that property is 10. Here is an example: 000000, 000011, 110000, 001100, 010010, 001111, 111100, 110011, 101101, 111111

I tried making some greedy solutions but they aren't working on greater n (and I think they can't be made accurate). When I thought of some graph solutions I reached an NP problem (let each binary number is vertex and we have an edge connecting them if they aren't "compatible"; now we have to find the maximum in vertices independent set). The other way I tried is making a bipartite graph with one set of vertices with the binary numbers of length n and the other with the binary numbers of length n-1. We have an edge from the first to the second set if the number from the second could be a substring of length n-1 of the number in the first. Now we have to find the maximum number of vertices from the first set so that their edges do not have any common endpoint vertex but I couldn't think out the solution of this problem and couldn't find it in the Internet.

$\endgroup$
  • $\begingroup$ 1. I edited my question. 2. I'm looking for the optimal answer. This task was given on a competition and that's my reason why this problem has to have a solution in polynomial time. 3. I found the problem when I was solving tasks for that competition. $\endgroup$ – Илиян Йорданов Feb 8 '15 at 6:46
  • $\begingroup$ Does anyone have any idea on the maximum degree of the corresponding graph (with a vertex for each string and an edge between each pair of compatible strings)? How large could the degree be, as a function of $n$? $\endgroup$ – D.W. Feb 8 '15 at 6:54
  • $\begingroup$ I think it is very large because for each vertex V it's (2^n-1)-t where t is the number of incompatible vertices with V and as you've said t is maximum 2*n*n. Which means for larger n (n>15) the number of edges of vertex V would be extremely high and the graph would be almost complete. $\endgroup$ – Илиян Йорданов Feb 8 '15 at 7:18
3
$\begingroup$

You seem to be looking for the optimal single-deletion-correcting code of length n. As far as I know, it's an open problem.

This paper states that

  1. The Varshamov-Tenengolts code (specifically $VT_0$) is a good candidate, but there has been no proof of this as of yet. It is the set of all words for which $\sum_{i=0}^{n} i\cdot x_i \equiv 0 \mod n+1$ where $x_i$ is the $i$-th digit in $x$'s binary representation. Its size can be computed as $$\frac{1}{2(n+1)}\sum_{d\mid n+1 \land 2\not \mid d} \phi(d)2^\frac{n+1}{d}$$. The first few values of the above formula can be found at A000016.

  2. The above code has been proven to be optimal for small values of $n$, and to be asymptotically optimal for large $n$.

  3. No efficient algorithm has been found to generate/check the optimal code. The largest value of $n$ for which an optimal code is known (and confirmed to be the above) is $9$ (actually $10$).

$\endgroup$

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.