3.5 Unstacking Game 강한 귀납법으로 증명하기
2020.10.14
블럭 $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)$이 참일 때,..