Invariants in Algorithms
이번 문제는 빈 상자 안에 빈 상자를 넣는 문제입니다.
11개의 큰 상자 중 몇 개의 각 상자 안에 중간 상자를 8개 넣을 수 있습니다.
다시 중간 상자 하나에는 작은 상자 8개를 넣을 수 있습니다.
이 과정을 몇 번 반복하여 빈 상자가 102개가 되었을 때 총 상자의 수는 몇 개일까요?
Variables
변수 설정에 앞서 문제 해결의 과정을 다음과 같이 진행하겠습니다.
- 최종 상태에 대해 알려진 것과 아닌 것 판단
- 임의의 시점에서의 상태를 나타낼 수 있는 변수 생성
- 상자에 상자를 넣는 과정을 변수에 값을 넣는 과정으로 모델링
- 이 과정에서 불변량 찾기
- 단서를 결합하여 문제 풀기
1번에 대해 알 수 있는 건 처음 시작할 때의 상자가 11개라는 것과 마지막 상태에서의 빈 상자가 102개라는 것입니다.
또 빈 상자 8개를 큰 상자에 넣게 되면 상자 수는 8개가 늘어나지만 빈 상자는 7개가 늘어나게 됩니다.
빈 상자의 수를 e, 총 상자의 수를 b라고 두었을 때 b, e := b+8, e+7이라는 식을 만들 수 있습니다. 이 식을 반복하는 것이 상자 안에 8개의 상자를 넣는 과정입니다.
문제에서 주어진 중간 상자, 작은 상자 등은 불필요한 세부사항에 포함됩니다. 과정을 몇 번 반복했는지는 변수로 추가할지 생략할지에 따라 풀이가 달라지게 됩니다.
이번엔 몇 번 반복했는지에 대한 부분도 생략해보겠습니다.
Invariants
이제 불변량을 찾아야 합니다.
불변량을 찾아내는 것은 어렵고 약간의 추측이 필요합니다.
상자를 넣는 과정을 반복하면 총 상자는 b0 + 8- b0 + 8*2-b0 + 8*3과 같은 등차 수열이 됩니다. 동일하게 빈 상자는 e0 + 7-e0 + 7*2-e0 + 7*3과 같이 증가하게 됩니다.
이제 약간의 추측이 필요합니다. 찾고자 하는 불변량도 위와 같이 선형적이라 가정하고 어떤 수 M, N에 대하여 M*b + N*e가 불변량이라고 생각해보겠습니다.
이제 (M*b + N*e)[b,e := b+8, e+7] = M*b + N*e라고 초콜렛 문제와 같이 식을 작성했습니다.
해당 식을 정리하면 8*M + 7*N = 0이 됩니다.
다시 식을 만족하는 M, N을 구해보면 M = 7 ∧ N = -8이 됩니다.
(물론 0이어도 가능하고, M이 -7, N이 8인 경우도 가능합니다. 다만 0인 경우는 모든 대입의 불변량이기에 문제 해결에 큰 도움이 되지 않습니다.)
Conclusion
이제 변수 설정과 불변량 구하기가 끝이 났습니다.
7*b - 8*e가 불변량이 됨을 알았으며 b, e의 초기값이 11임을 문제에서 알 수 있습니다.
이에 따라 7*b - 8*e의 값은 -11이 되고 이 값은 불변량이므로 대입이 몇 번 진행되더라도 값은 변하지 않습니다.
문제에서 주어진 e의 값은 102이므로 7*b -8*102 = -11이라는 식을 얻어낼 수 있습니다.
드디어 가장 빈 상자의 개수가 102개 일 때 총 상자는 115개임을 알아냈습니다.
Conditions for Generalization
빈 상자의 불변량을 가지고 문제를 일반화 해보겠습니다.
처음에 m개의 상자가 있고 k개의 상자를 넣을 수 있으며 마지막에 n개의 상자가 남았을 때 문제가 공식화 될 수 있는 m, k, n의 조건이 무엇이 있을까요?
위에서 구한 식을 토대로 변수로 치환해보면 다음과 같습니다.
대입식은 b, e := b+k, e+(k-1),
불변량은 (k-1)*b - k*e = -m이 됩니다.
이때 k=1인 경우 식이 항 하나가 0이 되어버리니 k의 조건은 2이상이어야 한다를 붙이고 총 상자의 수 b를 구하는 식을 도출하면 b = n + (n-m) / (k-1)이 됩니다.
이제 n은 최소 m이고 k는 2이상이어야 하며, n-m이 k-1로 나누어 떨어져야 합니다.
