자연계열 2-1번

과학자들은 지구에서 금성까지의 거리를 측정하기 위하여 레이더파를 금성에 쏘아 레이더파가 금성에 반사되어 되돌아오기까지의 시간을 재는 방법을 사용했다. 레이더파는 일종의 빛으로, 반사되어 올 때까지의 시간으로 금성까지의 거리를 알 수 있다. 그러나 단 하나의 펄스로 이루어진 레이더파는 공중의 수많은 전기에 영향을 받아 변형될 수 있으므로 과학자들은 일부가 왜곡되더라도 인식할 수 있는 일련의 패턴으로 이루어진 레이더파 펄스를 쏘아 보냈다. 그 패턴은 두 개의 문자로 이루어진 문자열에서 일정한 길이의 문자열이 반복되는 부분이 없도록 배열하는 방법을 사용한다. 이와 같은 문자열은 이동통신의 필수기술인 CDMA(코드분할 다중접속)방식에서도 사용된다. 코드분할 다중접속방식은 아날로그 형태인 음성을 디지털 신호로 전환한 후 여기에 난수를 부가하여 여러 개의 디지털 코드로 변환해 통신을 하는 것으로 이 방식을 사용하면 통화 품질이 좋고 통신 비밀이 보장된다는 장점이 있다.

그럼 두 개의 문자로 이루어진 문자열에서 일정한 길이의 문자열이 반복되는 부분이 없도록 배열하는 방법에 대하여 알아보자. 펄스의 패턴을 숫자로 이루어진 수열로 바꾸어 생각할 수 있다. 숫자들로 이루어진 수열에서 숫자의 개수를 수열의 ‘길이’라고 하자. 예를 들어 숫자 $\displaystyle 1$과 $\displaystyle 2$로 만들어진 수열 ‘$\displaystyle 112122112$’는 길이가 $\displaystyle 9$인 수열이다. 이 수열에 연속되는 세 숫자로 만들어진 세자리 수가 $\displaystyle 112$, $\displaystyle 121$, $\displaystyle 212$, $\displaystyle 122$, $\displaystyle 221$, $\displaystyle 211$, $\displaystyle 112$와 같이 $\displaystyle 7$개가 포함되어 있다. 그 중 $\displaystyle 112$는 두 번 포함되어 있고 그 외에 같은 수는 없다. 또 연속되는 다섯 숫자로 만들어진 다섯자리 수는 $\displaystyle 11212$, $\displaystyle 12122$, $\displaystyle 21221$, $\displaystyle 12211$, $\displaystyle 22112$로 다섯 개가 포함되어 있고 이 중 같은 수의 반복은 없다.

같은 두자리 수가 반복하여 나타나지 않는 수열 중 가장 긴 수열의 길이를 알아보자. 어떤 수열이 $\displaystyle 1$로 시작하면 그 다음 숫자는 $\displaystyle 1$이나 $\displaystyle 2$, 어느 것이나 올 수 있다. $\displaystyle 1$을 선택하여 $\displaystyle 11$을 만들면 그 다음에 오는 숫자는 $\displaystyle 2$가 되어야 한다. 만일 $\displaystyle 111$이면 연속되는 두 숫자로 만들어진 $\displaystyle 11$과 $\displaystyle 11$이 반복되기 때문이다. 이렇게 만들어진 수열 $\displaystyle 112$는 $\displaystyle 11$과 $\displaystyle 12$의 두자리 수를 포함하고 있다. 네 번째 오는 숫자가 $\displaystyle 1$이면 $\displaystyle 1121$로 이 수열은 같은 두자리 수를 포함하고 있지 않다. 한편 네 번째 오는 숫자가 $\displaystyle 2$이면 $\displaystyle 1122$로 이 경우도 같은 두자리 수를 포함하고 있지 않다. $\displaystyle 1121$에 다섯 번째 숫자를 붙여 보자. 그 다음에 오는 숫자가 $\displaystyle 1$이면 $\displaystyle 11211$로 $\displaystyle 11$이 반복되어 나타나고 그 다음에 오는 숫자가 $\displaystyle 2$이면 $\displaystyle 11212$로 $\displaystyle 12$가 반복되어 나타난다. 이제 $\displaystyle 1122$에 다섯 번째 숫자를 붙여 보자. 그 다음에 오는 숫자가 $\displaystyle 1$이면 $\displaystyle 11221$이고 이 수열은 같은 두자리 수를 포함하고 있지 않다. 따라서 길이가 $\displaystyle 5$인 수열 $\displaystyle 11221$은 같은 두자리 수가 반복하여 나타나지 않는 수열이다.

반복되는 두자리 수가 없는 길이가 $\displaystyle 6$인 수열을 만들 수 있을까? 길이가 $\displaystyle 6$인 수열에 반복되는 두자리 수가 없다고 가정해 보자. $\displaystyle 1$과 $\displaystyle 2$로 만들어지는 두자리 수는 $\displaystyle 11$, $\displaystyle 12$, $\displaystyle 21$, $\displaystyle 22$로 네 가지뿐이다. 그런데 길이가 $\displaystyle 6$인 수열의 처음 $\displaystyle 5$개의 숫자는 두자리 수의 앞자리 숫자가 되므로 그 $\displaystyle 5$개 중 하나는 다른 두자리 수와 중복될 수밖에 없다. 따라서 반복되는 두자리 수가 없는 가장 긴 수열의 길이는 $\displaystyle 5$이다.

또 한 가지 주목할 만한 사실은 위와 같이 모든 두자리 수를 단 한 번씩만 포함하고 있는 수열은 처음 숫자와 마지막 숫자가 같다는 것이다. 모든 두자리 수를 단 한 번씩만 포함하고 마지막 숫자가 $\displaystyle 1$인 수열을 생각하자. 만일 이 수열의 첫 숫자가 $\displaystyle 1$이 아니라면 $\displaystyle 1$로 시작하는 두자리 수인 $\displaystyle 11$과 $\displaystyle 12$는 맨 앞에 올 수 없으므로 수열의 중간 어디엔가 있을 것이다. 따라서 $\displaystyle 1$로 끝나는 수가 수열의 중간 어디엔가 두 번 나오게 된다. 그러나 이 수열의 맨 마지막 숫자가 $\displaystyle 1$이므로 이 수열은 $\displaystyle 1$로 끝나는 두자리 수를 $\displaystyle 3$개 포함하고 있다. 하지만 $\displaystyle 1$로 끝나는 두자리 수는 $\displaystyle 11$ 또는 $\displaystyle 21$로 두 가지밖에 없으므로 이 수열이 모든 두 자리 수를 단 한 번씩만 포함하고 있다는 가정에 모순이다. 따라서 이 수열의 첫 숫자는 $\displaystyle 1$이다.