Maior conjunto de números de 10 dígitos onde nenhum tem Distância de Hamming = 1 com qualquer outro

Question

Estou trabalhando em um sistema que exigirá a entrada manual de dados de números de 10 dígitos (Σ = 0123456789).Para ajudar a evitar erros de dados, quero evitar a geração de duas strings com uma distância de Hamming de 1.

Por exemplo, se eu gerar a string 0123456789, nunca desejarei gerar nenhuma destas strings:{1123456789, 2123456789, 3123456789, ...}

Qual é o maior conjunto de cadeias únicas no universo de cadeias possíveis que satisfazem a restrição em que não há duas cadeias com uma distância de Hamming igual a 1?Se este conjunto puder ser identificado, existe alguma maneira razoável de enumerá-lo?

Answer 1

Há uma solução simples:use exatamente as strings com somas de dígitos sendo divisíveis por $10$.Há $10^9$ tais strings e é fácil enumerá-las, encontre $i$-º deles na ordem lexicográfica, gera tal string aleatoriamente, etc.

Na verdade, se duas strings diferem exatamente em uma posição, então suas somas de dígitos também são diferentes módulo $10$.Por exemplo, as somas de dígitos para strings $0123456789$, $1123456789$, $\ldots$, $9123456789$ são $45$, $46$, $\ldots$, $54$ respectivamente.

Além disso, esta solução é a maior possível.Na verdade, existem $10^9$ tais cadeias:para todas as maneiras de escolher primeiro $9$ dígitos, existe exatamente uma maneira de escolher o último dígito para tornar a soma divisível por $10$.Portanto, existem $10^9$ cordas em nosso conjunto.

Por outro lado, qualquer conjunto de cordas com distância de Hamming mínima $2$ tem no máximo $10^9$ elementos.Na verdade, considere $10$ strings com um determinado prefixo de comprimento $9$.Todos eles estão dentro da distância de Hamming $1$ um do outro (porque diferem apenas na última posição).Portanto, no máximo um deles pode pertencer a qualquer conjunto “bom”.Portanto, qualquer conjunto “bom” contém no máximo $10^9$ elementos.