랭퍼드 배열(Langford paring)

어느날 스코틀랜드의 수학자 듀들리 랭퍼드(C. Dudley Langford)는 그의 아들이 컬러블록을 가지고 놀고 있는 것을 보고 있었다. 그러던 중 랭퍼드는 그의 아들이 배열한 세쌍의 컬러블록 (빨강, 파랑, 초록)이 두개의 빨간 블록은 한 블록만큼, 두개의 파란 블록은 두 블록만큼, 두개의 초록 블록은 세 블록만큼 떨어져 있는 것을 알게 되었다.

곧 그는 두개의 노란 블록을 더하여, 총 네 쌍의 컬러블록이 위와 같은 규칙을 갖도록 배열하는데 성공했다.

랭퍼드는 곧바로 이 문제의 일반화에 대해 흥미를 갖게 되었고 이 문제를 1958년에 발표하였다. 위 문제를 수학적으로 설명하면 다음과 같다:

$2n$개의 숫자 $1,\, 1,\, 2,\, 2,\, \ldots,\, n,\, n$을 아래의 규칙이 성립하도록 배열할 수 있을까?

임의의 $1 \leq k \leq n$에 대하여, $k$와 또 다른 $k$는 서로 정확히 $k$만큼 떨어져 있다.

따라서 $n=3$인 경우의 정답은 $3\,1\,2\,1\,3\,2$, 또한 $n=4$인 경우의 정답은 $4\,1\,3\,1\,2\,4\,3\,2$가 된다. 또한 이 정답은 숫자 배열을 뒤집는 것을 제외하면 유일함이 알려져 있다.

수을 $n$번째 항이 길이가 $2n$인 서로 다른 랭퍼드 배열의 개수라 하자. 그러면

\[ 0,\, 0,\, 1,\, 1,\, 0,\, 0,\, 26,\, 150,\, 0,\,0,\, 17792,\, 108144,\, \ldots \]

임이 알려져 있다. [OEIS 수열 A014552] 이 수열을 잘 보면, $n = 1,\,2,\,5,\,6,\,9,\,10$인 경우는 랭퍼드 배열이 존재하지 않음을 알 수 있다. 그렇다면 어떤 $n$에 대하여 적어도 하나 이상의 랭퍼드 배열이 존재할까? 또한 주어진 $n$에 대하여, 서로 다른 랭퍼드 배열의 개수는 구할 수 있을까?

정리.

만약 어떤 $n$에 대하여 랭퍼드 배열이 존재한다면, $n = 4m$ 또는 $n = 4m+3$ 꼴이다.

증명. $1,\,1,\,2,\,2,\,\ldots,\,n,\,n$의 숫자들로 이루어진 길이가 $2n$인 랭퍼드 배열이 있다고 하자. 이제 이 배열의 임의의 숫자 $1 \leq k \leq n$를 생각해 보자. 만약에 첫번째 $k$가 $P_k$번째 위치에 있다면, 두번째 $k$의 위치는 반드시 $P_k+k+1$이어야 한다. 이제 집합 $P$를 아래와 같이 정의하자.

\[ P = \set{P_k}{1 \leq k \leq n} \cup \set{P_k + k + 1}{1 \leq k \leq n}. \]

집합 $P$의 원소들은 길이가 $2n$인 랭퍼드 배열의 서로다른 위치를 각각 유일하게 나타내므로, $P$의 원소들의 합은 $1$부터 $2n$ 까지의 합과 같아야 한다. 따라서

\[ n(2n+1) = \sum_{k=1}^{n} \Big[ P_k + (P_k +k + 1) \Big] = 2 \sum_{k=1}^{n} P_k + \frac{n(n+1)}{2} + n. \]

위 식을 $P_k$의 합에 대하여 정리하면,

\[ \sum_{k=1}^{n} = \frac{1}{4}n(3n-1). \]

여기서 위 식의 좌변은 양의 정수이므로, 우변또한 양의 정수여야만 한다. 이제 $n= 4m$, $4m+1$, $4m+2$, $4m+3$을 각각 대입하여 우변이 양의 정수가 되는 경우를 살펴보면, $n = 4m$ 이거나 $n=4m+3$의 형태여야만 한다는 사실을 알 수 있다.

위 정리에 따르면 $n = 4m+1$ 또는 $n=4m+2$ 꼴인 경우 랭퍼드 배열이 존재하지 않음을 알 수 있다. 하지만 $n = 4m$ 또는 $n = 4m+3$형태의 모든 $n$에 대하여 랭퍼드 배열이 항상 존재하는지는 아직까지 알려지지 않았다. [OEIS 수열 A050998] 에는 모든 가능한 랭퍼드 배열을 크기순으로 배열해 놓았다.