3.5 Unstacking Game 강한 귀납법으로 증명하기

블럭 $n$개가 쌓여있다.

Unstacking Game은 해당 블럭을 더 이상 나눌 수 없을 때까지 $(a, n-a)$개로 나누어, 나누어진 블럭의 갯수의 곱을 내 점수에 더하여 점수를 측정한다고 한다.

예를들어, 블럭 5개를 (2개, 3개)로, 이를 각각 (1개, 1개), (2개, 1개)로, 마지막으로 (1개, 1개)로 나누었다면 내 점수는 $2\times3 + 1\times1 + 2\times1 + 1\times1 = 10$점이다.

그런데, $n$개의 블럭을 어떻게 나누든 점수가 $S(n)$이 된다는 것을 증명해보자.

Base case: $S(1) = 0$이다. 블럭 1개로 점수를 낼 방법이 없다.

이제 강한 귀납 명제를 풀어보자.

$P(1)\wedge \cdots \wedge P(n)$이 참일 때, $P(n+1)$이 참임을 증명하면 된다.

$S(n+1) = k\times (n+1-k) + s(k) + s(n+1-k)$이다.

$S(n) = \frac{n(n-1)}{2}$라고 추론하고, 이를 증명해보자.

$S(1) = 0, S(2) = 1$이며, $S(n+1)$은 다음과 같다.

$$\begin{align*}S(n+1) &= k(n+1-k)+\frac{k(k-1)}{2} + \frac{(n+1-k)(n-k)}{2}\\ &= \frac{2kn+2k-2k^2+k^2-k+n^2-nk+n-k-kn+k^2}{2}\\ &=\frac{n^2+n}{2} \end{align*}$$

우리의 추론이 맞았다! 귀납 명제가 증명되었다.