[궁금증 해결] 2α를 쪼개고 곱할 때, 왜 최댓값은 α × α일까?

서론

별 건 아니고, 샤워할 때 간단한 문제나 하나 풀고 있자~ 생각하면서 백준 14606번 피자 (small) 문제를 보고, 씻고 있었다.

 

대충 $N$개의 피자판이 쌓여 있을 때, 피자판을 둘로 나눈다. 예를 들어, $N$이 8이면 4와 4, 혹은 3과 5처럼 나눌 수 있다.

이때 나눠진 피자판의 개수를 서로 곱하면 즐거움이 나온다. 이걸 더이상 나눌 수 없을 때까지 반복한다. 

 

피보나치 저리가라 할 기초적인 DP 문제라 문제 자체는 쉬웠는데, 간단한 암산으로도 아래처럼 풀 수 있었다.

 

일단 즐거움이 제일 커져야 하니까, N를 2로 나눠서.... 그리고 곱한 값에 각 칸의 수를 더하면.... 

 

 

거기서, 갑작스레 든 의문. 왜 어떤 수를 쪼개서 곱할 때, 최댓값은 항상 균등할 때 나올까?

---

원리를 몰라도 습관처럼 했던 것들

우린 어떤 수 $K$가 주어질 때, 그 최댓값을 구하라면 자연스레 $K$를 반으로 나눈다. 제목은 짧게 적으려 $2K$라 했지만, 사실 홀수라도 다를 건 없다. $K \over 2$와, 거기에 1 더한 값으로 나눈다. 9는 4와 5로, 17은 8과 9로. 만약 소수까지 허용한다면, $K \over 2$로 쪼개는 게 최댓값이다. $4.5 \times 4.5 = 20.25$로, $4 \times 5 = 20$보다 크다.

 

이건 매우 자연스러운 흐름이다. 하지만 왜 그럴까? 모든 양수는 반으로 쪼갤 때 최댓값이 나올까? 가 궁금해져서, 그 자리에서 몇 가지 수학 지식을 총동원해봤다. 역시 샤워할 때 두뇌 회전이 가장 빠르다.

 

그리고, 꽤나 쉽게 정답을 알 수 있었다. 비밀은 합차 공식에 있었다.

 

간단한 설명을 위해, 어떤 수 $2K$가 있다고 하자. 이걸 반으로 나누면, 두 수는 모두 $K$가 된다. 즉, $K \times K = K^2$이 된다.

이번엔 조금 다르게 쪼개보자. $2K$를 각각 $(K + 1)$과 $(K - 1)$로 쪼갠다. 그리고 $(K + 1) \times (K - 1)$을 하면? 우리가 중학교 때 배운 합차 공식에 따라, $K^2 - 1$이 된다! (합차 공식이 뭔지 모른다면, 단순히 곱하기만 잘 해도 금방 알아낼 수 있다. $(K + 1) \times (K - 1) = K^2 + K - K - 1 = K^2 - 1$)

 

중앙에서 더 멀어지면 어떨까? $(K + 2)$와 $(K - 2)$로 쪼갠다면, $K^2 - 4$가 된다. 두 수의 밸런스가 붕괴될 수록, 중심에서 점점 멀어질수록, 수는 작아진다.

 

이는 홀수에도 똑같이 응용할 수 있다. 어떤 수 K가 존재할 때, 이를 정확히 절반, $K \over 2$으로 나눈다면, $({K \over 2})^2 - 0$으로 가장 큰 수가 된다. 중심에서 멀어질 수록 뒤의 빼는 수가 커질 뿐, 앞의 $({K \over 2})^2$엔 변함이 없다. 그렇기에, 최댓값은 얼마나 반으로 잘 쪼개냐?가 결정한다.

내친 김에 음수도 가보자. $-2K$를 $-K$로 나눈다면, $(-K + a) \times (-K - a) = K^2 - a^2$, 음수도 절반이 최댓값인 건 똑같다. (-는 제곱하면 사라지니까.)

 

조금 특수한 경우도 살펴보자. 만약 $K$가 0보다 크고, 1보다 작은 수라면 어떨까?

 

$K$를 0.5로 가정했을 때, 반으로 쪼개면 $0.25 \times 0.25$다. 중심에서 조금 멀어져볼까? $0.2 \times 0.3$으로 만든다면, 이는 $(0.25 - 0.05) \times (0.25 + 0.05) = (0.25)^2 - (0.05)^2 = 0.0625 - 0.0025 = 0.06$이 된다. 1보다 작은 양수에서도 이는 성립하므로, 모든 유리수에 대해 성립한다고 가정해도 될 것이다. (무한의 경우엔 잘 모르겠지만.)

 

무리수는 어떨까? $\sqrt{2}$를 반으로 쪼개면 $\sqrt{2} \over 2$. 이 경우에도, 유리수든 무리수든, 제곱하면 양수가 될 것이므로, 최댓값은 항상 절반이 된다.

 

그렇다. 제곱하면 양수가 되므로. 그렇다면 허수는 어떨까? 만약 어떤 수 $2K$가 있을 때, 이를 $(K + i)$와 $(K - i)$로 나눈다면, 이번엔 오히려 $K^2 - i^2 = K^2 + 1$이 되므로 절반으로 나눴을 때보다 커진다! 허수의 영역으로 간다면, $K^2$ 뒤에 오는 수는 항상 양수가 될 것이므로, 오히려 절반으로 나누면 최솟값이라는 결론이 나온다.

---

간단한 일반화

어떤 수 $A$가 존재할 때, $B + C = A$를 만족하는 $B$, $C$에 대해, 모든 수는 아래 규칙이 성립한다.

$D = {A \over 2}$에 대해, $B = D + E$, $C = D - E$로 나타낼 수 있으므로, $B \times C = (D + E) \times (D - E) = D^2 - E^2$이 성립한다.

 

이때, $E$가 실수라면 $B \times C$의 최댓값은 $D^2$이며, $E$가 허수라면 $B \times C$의 최솟값은 $D^2$가 된다.

$E$가 실수일 때, 최솟값은 무한하다. (단순히 $E$를 무한하게 키울 수록, 수는 점점 작아진다.)

$E$가 허수라면, 반대로 최댓값이 무한해진다. (위와 동일)

 

$D$의 값은 상관없다. 여기가 허수가 된다한 들, 어차피 고정된 값이고, 뒤에 빼는 수인 $E$가 핵심이다.

---

마무리

이렇게, $E$가 실수인 상황이라면, 어떤 수 $A$를 둘로 쪼개고 곱할 때 최댓값은 항상 반으로 쪼갤 때라는 걸 알 수 있다. 이제 알고리즘 문제를 풀 때, 마음 놓고 반으로 가르고 시작하자!