Problems and Solutions #015

Problem #015

$7$개의 자연수로 이루어진 순서쌍 $a = (a_1,\, a_2,\, \ldots,\, a_7)$를 생각하자. 또한 순서쌍 $b = (b_1,\,b_2,\, \ldots,\, b_7)$를 $a$의 각 성분을 치환(permute)하여 얻은 새로운 순서쌍이라 하자. 이때 아래의 값

\[ (a_1-b_1)(a_2-b_2) \cdots (a_7-b_7) \tag*{$(\ast)$}\]

의 값은 언제나 짝수가 됨을 증명하여라.

예를 들어, $a = (3,\,1,\,4,\,1,\,5,\,9,\,2)$이고 $b = (1,\,9,\,2,\,3,\,4,\,5,\,1)$라 하면,

\[ (3-1)(1-9)(4-2)(1-3)(5-4)(9-5)(2-1) = 256 \]

이 되어 짝수가 된다.

임의의 자연수 순서쌍 $a = (a_1,\, a_2,\, \ldots,\, a_7)$와 $a$의 각 성분을 임의로 치환하여 얻은 새로운 자연수 순서쌍 $b = (b_1,\,b_2,\, \ldots,\, b_7)$을 생각하자. 또한 식 $(\ast)$의 결과가 홀수라 가정해 보자. 

두 자연수의 곱의 결과가 홀수인 경우는 홀수×홀수일 때 밖에 없으므로, 모든 $n=1,\,2,\, \ldots,\, 7$에 대하여 $(a_n-b_n)$이 홀수임을 알 수 있다. 이제 각각의 $n$에 대하여 $(a_n-b_n)$이 되기 위해서는 $a_n$과 $b_n$의 홀짝성(parity)이 달라야만 함을 알 수 있다. 즉, $a_n$이 짝수이면 $b_n$은 홀수이고, 반대로 $a_n$이 홀수이면 $b_n$은 짝수여야만 한다. 

이제 $a$의 성분 중 짝수인 성분의 개수를 $k$, 홀수인 성분의 개수를 $(7-k)$라 하자. (단, $k$는 $0 \leq k \leq 7$인 정수이다.) 그러면 $b$의 성분 중 짝수인 성분의 개수는 $(7-k)$, 홀수인 성분의 개수는 $k$가 되어야 한다. 하지만 $b$는 $a$의 성분을 치환하여 얻은 것이므로, $a$와 $b$의 각 성분 중 짝수인 성분의 개수와 홀수인 성분의 개수가 서로 같아야만 한다. 따라서 $7-k = k$이고 따라서 $k = 3.5$가 된다. 하지만 이는 $k$가 정수라는 사실에 모순이다. 

결과적으로 식 $(\ast)$의 결과는 짝수여야만 한다.