3.5 귀납법을 통한 문자 퍼즐 문제 증명

아래와 같은 타일로 이루어진 퍼즐을 생각해보자.

빈 칸으로 다른 타일을 움직여 퍼즐의 모양을 바꿀 수 있다. 이때, 다른 타일의 위치는 모두 유지한 채 H와 G의 위치만 바꿀 수 없음을 수학적 귀납법을 통해 증명해보자.

$$\text{Lemma 1. Row move does not change the order.}$$

같은 행에서의 이동은, 순서를 바꾸지 않는다. (H 빈칸 G)나 (H G 빈칸), (빈칸 H G) 모두 알파벳 순서는 바뀌지 않았다.

$$\text{Lemma 2. Column move does change the relative order of 2 pairs of letters.}$$

그러나 열 이동은 2 쌍의 알파벳의 순서를 바꾼다. 예를들어, F의 위치를 $i$라 할 때, F가 아래로 내려오면 ($i+1, i+2$)였던 G와 H의 순서는 ($i-2, i-1$)이 된다.

$$\text{Def. The pair of the alphabet A1 and A2 is  inverted pair. If L1 precedes L2 in alphabetical order, but does not in puzzle) $$

알파벳 순으로는 L1이 L2 앞이나, 그 반대로 배치된 쌍을 inverted pair라고 부르기로 해보자. (예를들어, 퍼즐 상에 B A가 있는 경우)

행 이동은 알파벳의 순서를 바꾸지 않기 때문에($\text{Lemma 1}$), 행 이동에서는 inverted pair의 갯수가 변하지 않는다.

열 이동은 알파벳 2개와 한 알파벳의 상대적 위치가 변화하므로(\text{Lemma 2}$), inverted pair는 2개 단위로 늘어나거나, 줄어든다.

열 이동으로 2개의 알파벳과 하나의 알파벳의 상대적 위치가 변화하여 inverted pair 갯수가 변화하는 경우는 3가지 있는데,

1. 두 알파벳 모두 이동한 알파벳의 앞이라 inverted pair가 2개 추가

2. 두 알파벳 모두 이동한 알파벳의 뒤라 inverted pair 2개 감소

3. 하나는 전자, 하나는 후자라 inverted pair가 1개 증가하고 1개 감소하여 변화 없음

어떤 수에 2를 더하거나 빼서 홀짝을 바꿀 수 없으므로 아래 추론이 유도된다.

$$\text{Corollary 1. During the move, the pairty of number of inverted pair doesnt' change}$$

$\text{Corollary 1}$에 의해, ABCDEFHG는 inverted pair가 하나로 홀수이고, ABCDEFGH는 inverted pair가 0개 이므로, ABCDEFGH에서 ABCDEFHG로의 변환은 불가능하다.

귀납 명제

ABCDEFGH에서 $n$회 이동을 통해 ABCDEFHG로 만들 수 없음을 귀납법으로 증명하자.

$P(n)$이 ABCDEFGH에서 $n$회 이동한 결과, inverted pair가 짝수임을 뜻한다고 하자.

$P(0)$은 참이다. (이동이 없으므로)

우리는 $\text{Corollary 1}$에 의해, 1회의 이동이 inverted pair의 홀짝을 바꾸지 않음을 안다. 그러므로 $P(0)$이 참이라면, $P(1)$도 참이다. 즉, $P(n) \Rightarrow P(n+1)$이 성립한다.

수학적 귀납법에 의해 $P$가 모든 자연수 $n$에 대해 성립함이 밝혀진 것이다.