곱이 최대가 되도록 주어진 수를 분할하는 방법

나는 초등학교 때 수학 학원에 다녔다. 이때는 교과과정 선행학습 대신 사고력 문제와 퍼즐 등을 위주로 공부했다. 단골 주제는 정수론과 조합론이었다. 이때는 삼각함수, 로그함수나 미적분 같은 것은 전혀 몰랐지만, 정수론과 조합론 실력은 글을 쓰고 있는 지금의 나보다도 나았을 것으로 생각한다(사실 그때 이후로 저 분야를 별로 공부하지 않아 유난히 못하는 것이기도 하다).

이때 공부한 내용들은 대부분 잊어버렸지만, 아직도 기억하는 문제가 있다. 그것은 바로 다음과 같다.

자연수 $N$이 주어졌을 때, 곱이 최대가 되도록 $N$을 분할하는 방법을 찾아라.

여기서 $N$을 분할한다는 것은 총합이 $N$인 여러 개(한 개도 가능)의 수로 만드는 것을 의미한다. 예를 들어, $N = 5$인 경우 $1 + 2 + 2$, $1 + 4$, $2 + 3$, $5$ 등으로 분할할 수 있다. 이때 분할된 수들의 곱이 최대인 것을 찾는 것이다. $N = 5$인 경우 $2 \cdot 3 = 6$이 최대이다. $N = 6$인 경우 $3 \cdot 3$이 최대, $N = 7$인 경우 $3 \cdot 2 \cdot 2$와 $3 \cdot 4$가 최대이다.

문제를 형식적으로 기술하면, 모든 $i = 1, \ldots, n$에 대해 $x_i \in \mathbb{N}$이고 $x_1 + \cdots + x_n = N$을 만족하는 $n$과 $(x_1, \ldots, x_n)$을 찾으라는 것이다.

이 문제는 언뜻 보면 어려워 보이지만, 사실 몇 가지 간단한 관찰을 통해 쉽게 풀 수 있다. 여러 $N$에 대해 해답을 직접 구해보면 대부분이 $3$으로 구성됨을 관찰할 수 있다. 예를 들어 $14$의 경우 $3 \cdot 3 \cdot 3 \cdot 3 \cdot 2$가 해답이다. 그리고 이것의 이유에 대해 생각을 하다 보면, $5$ 이상의 수는 $2$와 $3$으로 분할했을 때 곱이 더 커지고, $2 \cdot 2 \cdot 2 < 3 \cdot 3$이므로, 결국 다른 수들은 대부분 $3$으로 교체되어 버림을 알아차릴 수 있을 것이다. 구체적인 풀이는 아래에 따로 서술할 것이지만, 이것이 핵심 아이디어인 것은 다르지 않다. 이 문제가 지금까지 기억에 남은 것도 이런 간단한 발상으로 예상치 못하게 간단히 풀린 것에 대한 놀라움에 있는 것 같다.

이 문제는 처음 본 이후로 한참 동안 까먹고 있었다가, 어느 날 문득 떠오르게 되었다. 정확한 이유는 기억나지 않지만 아마 최적화 문제에 관해 공부하다가 과거의 기억을 떠올리게 된 것 같다. 그러나 이 문제를 처음 봤을 그 당시와는 상당히 다른 관점으로 바라보았다. 그것은 상수 $e$와의 연관성에 대한 추측이었다. 앞에서 말했듯이 이 문제의 답은 대략 최대한 많은 $3$으로 분할하는 것으로 요약된다. 그런데 $3$은 $e = 2.718\ldots$와 가장 가까운 자연수이다. 그리고 이런 부류의 문제에서는 답이 $e$와 관련된 경우가 상당히 많다. 이 문제의 경우 자연수로만 분할이 가능하므로 $e$가 직접 답에 나올 수는 없지만, 그 대신 가장 가까운 $3$이 최적해로 나오게 된 것이 아닌가 추측하였다. 문제를 처음 봤을 때는 $e$의 존재조차 몰랐으므로 이런 생각을 할 수 없었지만, 다시 떠올렸을 때는 이미 $e$에 익숙해져 있었기 때문에 이런 연결이 자연스러웠다.

그래서 만약에 분할의 범위를 자연수가 아니라 실수로 확장한다면 더 직접적으로 $e$와 관련이 있게 될 것으로 생각하였다. 이를 확인하기 위해 문제를 설정하고 다시 풀어볼까 생각했었지만 귀찮아서 하지 않고 있다가, 이제서야 제대로 하게 되었다.

원 문제의 풀이

앞에서 말한 통찰을 더 자세하고 명확하게 분석한다면 해답을 얻을 수 있다.

우선 이 문제는 greedy 하다는 것을 알 수 있다. 예를 들어 $13$을

\[13 = 2 + 5 + 1 + 5\]

로 분할했다고 하자. 여기서 앞의 $2$와 $5$를 $3$과 $4$로 교체하여

\[13 = 3 + 4 + 1 + 5\]

로 만들자. 그러면 $2 \cdot 5 < 3 \cdot 4$이므로 분할의 곱은 더 커지게 된다. 이때 나머지 부분 $1 + 5$가 무엇인지는 전후 곱의 대소 관계에 영향을 주지 않는다.

이 사실을 일반화하면, 분할의 일부분이 최대 곱을 가지지 않는다면 이를 더 큰 곱의 분할로 교체할 수 있음을 알 수 있다. 따라서 문제의 해답은 분할의 모든 일부분 역시 최대 곱을 가져야 한다. 이 특성을 보여주는 예로, $N = 7$에 대한 해답 중 하나인 $7 = 3 + 2 + 2$을 살펴보자. 여기서 부분 분할인 $5 = 3 + 2$나 $4 = 2 + 2$를 선택하면, 이들 역시 각각 $N = 5$, $N = 4$인 경우에서의 해답임을 알 수 있다.

그다음 관찰은, 위 조건을 만족하기 위해서는 결국 정해진 수 몇 개의 조합으로 환원되어야 한다는 것이다. 일단 $5$ 이상의 수의 경우, 그대로 쓰지 않고 분할하는 것이 항상 곱을 더 커지게 한다. $5$ 이상의 정수 $a$는 $\lfloor a/2 \rfloor$, $a - \lfloor a/2 \rfloor$로 분할했을 때 곱이 더 커지기 때문이다($\lfloor x \rfloor$는 $x$보다 크지 않은 최대 정수이다). 다음은 그 예시이다.

\[5 < 2 \cdot 3 = 6 \\ 6 < 3 \cdot 3 = 9 \\ 7 < 3 \cdot 4 = 12 \\ \cdots\]

따라서 $5$ 이상의 수는 해답에 절대 포함될 수 없다.

반면 $1$의 경우 trivial case인 $N = 1$인 경우를 제외하고는 다른 수와 합쳤을 때 항상 곱이 더 커진다. $a + 1 > a \cdot 1$이기 때문이다. 따라서 ($N = 1$을 제외하면) $1$ 역시 해답에 절대 포함될 수 없다.

따라서 남은 수는 $2, 3, 4$밖에 없다. 또한 $4$의 경우 항상 $2 + 2$로 분할할 수 있으므로, $4$를 포함한 답은 항상 $2$를 포함한 답으로부터 구해질 수 있다(예: $7 = 3 + 2 + 2 = 3 + 4$). 따라서 편의상 $2$, $3$만을 고려할 것이다.

그리고

\[8 = 2 \cdot 2 \cdot 2 < 3 \cdot 3 = 9\]

임을 관찰할 수 있다. 즉 $2$가 3개 이상 있는 경우 이를 2개의 $3$으로 바꾸어 곱을 더 크게 할 수 있으므로 해답이 아니다. 따라서 해답은 대부분 $3$으로 구성될 것임을 짐작할 수 있다. 이제 해답이 정확히 어떻게 표현되는지 분석할 것이다.

$N = 3M + K$로 표현하자. $K \neq 1$인 경우

\[\begin{align*} 3M + 0 &= 3 + \cdots + 3 \\ 3M + 2 &= 3 + \cdots + 3 + 2 \\ \end{align*}\]

이 최대임을 알 수 있다. 여기서 $3 + \cdots + 3$은 $3$이 $M$번 더해진 것을 의미한다. $2$, $3$만이 허용되는 현재 상황에서는 $3 + 3$을 $2 + 2 + 2$로 바꾸는 것 외에는 수정 가능한 것이 없으며, 이는 앞에서 말한 대로 곱을 줄이기 때문에 불가능하다. $K = 1$인 경우

\[3M + 1 = 3 + \cdots + 3 + 2 + 2\]

이 최대이다. 여기서는 $3 + \cdots + 3$이 $3$을 $M - 1$번 더하는 것을 의미한다.

이렇게 해답이 완전히 구해졌다. 이를 정리해서 나타내면 다음과 같다. $N$을 $3$으로 나눈 나머지가 $1$인 경우, $2 + 2$를 남겨놓고 나머지를 모두 $3$으로 분할한다. 이외에는 최대한 많은 $3$으로 분할하고 남은 수($2$)가 있다면 추가한다.

범위를 실수로 확장한 경우

이제 이 문제를 실수 범위로 확장할 것이다. 이를 위해 우선 문제를 명확히 정의할 필요가 있다. 문제는 다음과 같다.

양의 실수 $N$이 주어졌을 때, 곱이 최대가 되도록 $N$을 양의 실수로 분할하는 방법을 찾아라.

형식적으로 기술하면, 모든 $i = 1, \ldots, n$에 대해 $x_i > 0$이고 $x_1 + \cdots + x_n = N$을 만족하는 $n$과 $(x_1, \ldots, x_n)$을 찾으라는 것이다.

풀이

이 문제도 어려워 보일 수 있지만, 사실 원 문제처럼 간단하게 풀릴 수 있다. 그러나 자연수에서 실수로 확장됨에 따라 풀이 방식에는 상당히 차이가 있다.

이 문제를 한 번에 푸는 것은 어려워 보이므로, 최대화 문제를 두 개로 분리하여 풀 것이다. $D(N, n)$을 가능한 모든 $n$조각 분할 방법 $(x_1, \ldots, x_n)$의 집합이라고 하자. 그러면 문제를 중첩된 최대화 문제

\[A = \max_{n \in \mathbb{N}} \max_{ (x_1, \ldots, x_n) \in D(N, n)} \prod_{i=1}^n x_i\]

로 쓸 수 있다. 먼저 주어진 $n$에 대해 안쪽의 최댓값을 먼저 구하고, 그다음 바깥쪽 문제를 풀어 최종 답을 구할 것이다.

산술-기하 평균 부등식(Arithmetic-Geometric Mean Inequality)에 의해

\[N = x_1 + \cdots + x_n \ge n \sqrt[n]{x_1 \ldots x_n}\]

이 성립하며, 등호성립조건은 $x_1 = \cdots = x_n = N / n$이다. 따라서 $x_1 \ldots x_n$은 이때 최댓값을 가지며, 그 값은

\[\left( \frac{N/n + \cdots + N/n}{n} \right)^n = \left( \frac{N}{n} \right)^n\]

이다.

이를 본 문제에 대입하면

\[A = \max_{n \in \mathbb{N}} \left( \frac{N}{n} \right)^n\]

가 된다. 자연수 범위에서 최댓값을 바로 찾기는 어려우므로, 먼저 $n$의 범위를 실수로 확장하여 $f(x) = (N/x)^x$이 최댓값을 가지는 점을 찾고 이를 바탕으로 자연수 범위에서의 최댓값을 구할 것이다.

$f(x)$의 도함수는

\[f'(x) = \left( \frac{N}{x} \right)^x \left( \log \left( \frac{N}{x} \right) - 1 \right)\]

이다. 도함수는 $x = N/e$에서 부호가 양에서 음으로 바뀐다. 따라서 $f(x)$는 이 점에서 최댓값을 가진다.

그러나 $x = N/e$는 $N$이 $e$의 정수배가 아닌 경우 자연수가 아니므로, 자연수 범위에서 최댓값을 다시 구할 필요가 있다. $f(x)$는 $x = N/e$에서 멀어질수록 감소하므로, $N/e$의 좌우에 있는 가장 가까운 자연수가 후보이다. 예를 들어 $N/e = 2.5$면 최대점 후보는 $x = 2, 3$이고, $N/e = 0.5$면 후보는 $x = 1$이다. 후보가 1개이면 그것이 곧 최대점이지만, 2개인 경우 둘 중에 어느 것이 최대점인지 바로 알아내기는 어려워 보인다. ($x = N/e$에 더 가까운 것이 최대점이라는 보장은 없음에 유의하자. $f(x)$의 그래프를 보면 최대점을 중심으로 대칭인 것 같지만 실제로 완벽한 대칭은 아니다.) 그러나 값 2개만 계산해서 비교하면 되므로 큰 문제는 아닌 것 같다.

$x_i = N/x$이고 $x$가 $N/e$에 가까운 정수이므로 $x_i$는 $N/(N/e) = e$에 가까운 수가 된다. 결론적으로, 곱이 최대가 되도록 $N$을 분할하는 방법은 각 조각이 최대한 $e$에 가깝도록 균등하게 분할하는 것이다. 이것은 앞에서 말한 통찰과 일치한다.

결론

이 문제의 자연수 버전과 실수 버전의 해답은 $e$를 중심으로 밀접하게 연관되어 있음을 보였다. 흥미로운 점은 두 문제의 접근 방식은 매우 달랐다는 것이다. 자연수 세계와 실수 세계 간의 신비로운 연관성을 보여주는 사례로 볼 수도 있을 것 같다.