3.5 Unstacking Game 강한 귀납법으로 증명하기
2020.10.14
블럭 n개가 쌓여있다. Unstacking Game은 해당 블럭을 더 이상 나눌 수 없을 때까지 (a,n−a)개로 나누어, 나누어진 블럭의 갯수의 곱을 내 점수에 더하여 점수를 측정한다고 한다. 예를들어, 블럭 5개를 (2개, 3개)로, 이를 각각 (1개, 1개), (2개, 1개)로, 마지막으로 (1개, 1개)로 나누었다면 내 점수는 2×3+1×1+2×1+1×1=10점이다. 그런데, n개의 블럭을 어떻게 나누든 점수가 S(n)이 된다는 것을 증명해보자. Base case: S(1)=0이다. 블럭 1개로 점수를 낼 방법이 없다. 이제 강한 귀납 명제를 풀어보자. P(1)∧⋯∧P(n)이 참일 때,..