거리가없는 10 자리 숫자의 가장 큰 10 자리 숫자 세트= 1 다른 것과 함께 1

Question

10 자리 숫자 (σ= 0123456789)의 수동 데이터 입력이 필요한 시스템에서 작업하고 있습니다.데이터 오류를 방지하기 위해 1 캠핑 거리가 1의 거리가있는 두 개의 문자열을 생성하지 않으려면

예를 들어 0123456789를 생성하면 다음 문자열 중 하나를 생성하지 않으려고합니다. {1123456789, 2123456789, 3123456789, ...}

두 문자열이 1의 캠핑 거리가없는 제약 조건을 만족시키는 가능한 문자열의 유니버스에서 가장 큰 독특한 문자열 집합은 무엇입니까?이 세트를 식별 할 수있는 경우, 열거 할 수있는 합리적인 방법이 있습니까?

Answer 1

간단한 솔루션이 있습니다. $ 10 $ 에서 나눌 수있는 숫자 합계가있는 문자열을 정확하게 사용하십시오. $ 10 ^ 9 $ 그런 문자열이 있으며, $ i $ 을 찾는 것이 쉽습니다. 그들 중에서 사전 판결의 순서로 무작위로, et cetera.

실제로 두 개의 문자열이 정확히 한 위치가 다를 경우, 숫자의 합계는 다른 Modulo $ 10 $ 입니다. 예를 들어 문자열 $ 0123456789 $ 0123456789 $ , $ 1123456789 $ , $ \ ldots $ , $ 9123456789 $ 9123456789 $ 은 $ 45 $ , $ 46 $ , $ \ ldots $ , $ 54 $

이 솔루션이 가장 크다. 실제로 $ 10 ^ 9 $ 문자열 : 첫 번째 $ 9 $ 숫자를 선택하는 모든 방법이 있습니다. $ 10 $ 에서 합계를 나눌 수있는 마지막 숫자를 선택하는 정확한 편도입니다. 따라서 $ 10 ^ 9 $ 문자열이 있습니다.

다른 한편으로, 최소한의 해밍 거리 $ 2 $ 은 $ 10 ^ 9 $ 요소. 실제로 $ 10 $ $ 9 $ 의 주어진 접두사를 가진 $ 10 $ 문자열을 고려하십시오. 그들은 모두 캠프 거리 $ 1 $ (마지막 위치에서만 다르기 때문에) 내에 있습니다. 따라서 대부분의 것들은 어떤 "좋은"세트에 속할 수 있습니다. 따라서 "좋은"세트는 대부분의 $ 10 ^ 9 $ 요소를 포함합니다.