[2월의 퍼즐 해설] 2018년을 보내며

정답은 \(m=56\), \(n=1850\)이다. 이때 \(m^m\)은 \(2^{168}\)을 약수로 가지고 \(n^n\)은 \(2^{1850} \times 5^{3700}\)을 약수로 가지므로, \(m^m n^n\)을 계산하면 마지막 2018개의 자리에 0이 나타난다.

이 문제에서 \(m^m n^n\)을 소인수분해할 때 2와 5 가운데 하나는 2018개가 나타나야 하고, 다른 하나는 2018와 같거나 그보다 많이 나타나야 한다. 쉽게 생각할 수 있는 답 가운데 하나는 \(m = 2018\)로 두는 것이다. 그러면 \(m^m\)에는 소인수 2가 2018개가 있으므로, \(n\)은 2018보다 크면서 홀수인 5의 배수를 아무 것이나 골라도 된다. 예를 들어, \(m=2018\), \(n=2025\)를 생각할 수 있다. 조금 줄여 보면, \(n = 625 = 5^4\)로 두면 \(n^n = 5^{4 \times 625}\)가 되고 \(4 \times 625 > 2018\)이므로,
\[
m = 2018, \qquad n=625
\]
도 조건을 충족하는 예가 되며, \(n\)을 이보다 더 작게 만들 수는 없다.

이제 2와 5를 \(m\)과 \(n\)이 나누어 가지는 경우를 생각해 보자. 2018은 5의 배수가 아니므로, \(m^m n^n\)의 소인수분해에서 5를 2018개 나타나게 할 수는 없다. 따라서 2018개의 2가 \(m^m\)과 \(n^n\)에 나누어 나타나는 경우를 생각하면 된다. 그리고 이때 \(m\)과 \(n\) 가운데 어느 하나는 5의 배수가 되어야 하므로, \(m^m\)의 소인수분해에는 짝수 개의 2가 나타나고 \(n^n\)의 소인수분해에는 10의 배수만큼의 2가 나타난다고 생각해도 된다. 즉, \(m\)은 5의 배수가 아닌 짝수, \(n\)은 10의 배수인 경우를 생각하면 된다.

예를 들어 보면, \(n=1000=2^3 \times 5^3\)이라면 \(n^n\)의 소인수분해에는 \(2^{3 \times 1000}\)이 나타나므로, 2는 2018보다 훨씬 많이 나타난다. \(n=400 = 2^4\times5^2\)을 생각해 보면, \(2^{4 \times 400}\)으로부터 \(n^n\)에는 \(2\)가 1600개가 있음을 알 수 있다. 이것은 2018을 넘지 않아서 \(m^m\)에서 \(2018-1600=418\)개의 2를 더 만들면 되지만, 이 경우 \(n^n\)에는 \(5^{2 \times 400}\)으로 5가 800개밖에 나타나지 않아 조건을 충족하지 않는다.

이런 식으로 생각하면 우선 보너스 문제의 2019는 불가능함을 알 수 있다.

\(i)\) 이제 조건에 맞는 \(m\)과 \(n\)을 찾기 위해, 먼저 \(n\)이 5의 배수이면서 \(25\)의 배수는 아닌 경우를 생각해 보자. 이것을 \(5\,\|\,n\)으로 나타낸다. 이 경우 \(n^n\)에는 \(5\)가 \(n\)개 있으므로, \(n \ge 2018\)이고 \(5\,\|\,n\)이라는 사실과 \(n\)이 짝수라는 가정으로부터 \(n \ge 2020\)이 되어야 한다. 그런데 이 경우 \(n^n\)에는 2가 2020개보다 더 많거나 같게 나타나므로 \(m^m n^n\)에 2가 2018개 나타날 수는 없다. 따라서 \(n\)은 50의 배수가 되어야 한다.

\(ii)\) 이제 \(n\)이 \(25\)의 배수이고 \(125\)의 배수가 아닌 경우를 생각해 보자. 이때, \(n^n\)에는 \(5\)가 \(2n\)개 있으므로, \(\ge 2018\)이고 \(5^2\,\|\,n\)이라는 사실과 \(n\)이 짝수라는 가정으로부터 \(n\)으로 가능한 값은
\begin{align*}
&1050, 1100, 1150, 1200, 1300, 1350, 1400, 1450, 1550, \\
&1600, 1650, 1700, 1800, 1850, 1900, 1950, 2050, \dots
\end{align*}
등이다. 이 가운데 \(n \ge 2050\)인 경우에는 \(n^n\)에 2가 2018개보다 많아지므로 고려할 필요가 없다.

첫 번째 후보인 \(n=1050\)을 생각해 보면, \(m^m n^n\)에 2가 2018개 있으려면 \(m^m\)의 소인수분해에 \(2018-1050 = 968\)개의 \(2\)가 있어야 한다. 그러면 적당한 홀수 \(a\)에 대하여 \(m = 2^r a\)일 때, \(m^m\)의 소인수분해에는 2가 \(r \times 2^r a\)개 있으므로, \(r \times 2^r\)이 968을 나누고 그 몫은 2로 나누어지지 않는 경우를 찾아야 한다. 968은 8로 나누어지므로, 968을 나누는 \(\times 2^r\)은 \(3 \times 2^3\)이거나 \(2 \times 2^2\)이어야 한다. 그런데 3은 968을 나누지 못하므로, 결국 \(m = 968/2 = 484 = 2^2 \times 121\)이라야 하고 이때 \(m^m = 2^{2 \times 484} 121^{484}\)가 된다. 그러면 \(mn = 484 \times 1050 < 625 \times 2018\)이므로 곱이 더 작은 답으로
\[
m = 484, \qquad n = 1050
\]
을 찾았다.

이어서, \(n = 1100\)을 생각해 보면, \(2^2 \,\|\, n\)이므로 이번에는 \(n^n\)의 소인수분해에 2가 \(2 \times 1100\)개가 있게 되어 2018보다 더 많아진다. 따라서 \(n=1100\)인 경우는 생각할 필요 없다. 같은 식으로, \(n\)이 4로 나누어지는 1200, 1300, 1400, 1600, 1700, 1800, 1900도 모두 고려할 필요가 없다.

만약 \(n = 1150\)이라면, \(m^m\)의 소인수분해에는 2가 \(2018-1150 = 868\)개가 있어야 한다. 868은 4로 나누어지지만 8로는 나누어지지 않으므로, \(868\)을 나누는 \(r \times 2^r\)은 존재하지 않는다. 따라서 \(n=1150\)인 경우도 불가능하다.

다음 후보인 \(n=1350\)의 경우, \(m^m\)의 소인수분해에는 2가 \(2018-1350=668\)개가 있어야 하고, 앞서와 마찬가지로 \(668\)을 나누는 \(r \times 2^r\)은 존재하지 않는다. 같은 이유로 \(n = 1550, 1950\)도 고려할 필요 없다.

이제 후보로 \(n = 1450, 1650, 1850\) 셋이 남는다.

만약 \(n = 1450\)이라면, \(m^m\)의 소인수분해에는 2가 \(2018-1450 = 568\)개가 있어야 하고, \(2^3\,\|\,568\)이므로 \(568\)을 나누는 \(r \times 2^r\)은 \(3 \times 2^3\)이거나 \(2 \times 2^2\)이어야 한다. \(568\)은 3으로 나누어지지 않으므로, \(r = 2\)이고 \(m = 568/2 = 284\)가 된다. 이때 \(mn = 284 \times 1450\)이므로
\[
m = 284, \qquad n = 1450
\]
은 앞서 찾은 \(m = 484, n = 1050\)보다 곱이 더 작은 답이 된다.

다음으로 \(n = 1650\)인 경우를 생각해 보자. 이 경우 \(m^m\)의 소인수분해에는 2가 \(2018-1650 = 368\)개가 있어야 하고, \(2^4\,\|\,368\)이므로, \(368\)을 나누는 \(r \times 2^r\)은 존재할 수가 없다.

마지막으로 \(n = 1850\)을 생각해 보자. 이번에는 \(m^m\)의 소인수분해에 2가 \(2018-1850 = 168\)개가 있어야 한다. \(2^3 \,\|\, 168\)이므로, 168을 나누는 \(r \times 2^r\)은 \(3 \times 2^3\)이거나 \(2 \times 2^2\)이어야 한다. 이번에는 168이 3의 배수이므로, \(m = 168/3 = 56\)과 \(m = 168/2 = 84\)의 두 가지 경우가 가능하고, 이 가운데 \(m\)과 \(n\)의 곱이 작은 쪽은 \(m = 56\)일 때이다. 그리고 이때, \(mn = 56 \times 1850 < 284 \times 1450\)이므로
\[
m = 56, \qquad n = 1850
\]
은 곱이 더 작은 답이 된다.

\(iii)\) 이번에는 \(n\)이 \(5^3\)으로 나누어지는 경우를 생각해 보자.

이 경우 \(n^n\)의 소인수분해에서 \(5\)는 적어도 \(3n\)개가 나타난다. 그러면 \(3n \ge 2018\)을 만족하는 \(n\)은 \(750, 1000, 1250, 1500, 1750, 2000, 2150, \dots\)이 가능하다. 이때 \(n \ge 2150\)이면 \(n^n\)에 2가 \(2018\)개보다 많이 나타나므로 고려할 필요 없다. 한편 \(n\)이 4의 배수이고 \(n \ge 1500\)이면, \(n^n\)에는 \(2 \times 1500 = 3000\)개 이상의 2가 나타나므로 이 경우도 고려할 필요 없다. 따라서 가능한 후보는 \(n = 750, 1000, 1250, 1750\)이다. 여기서 \(n = 1000\)은 \(8\)로 나누어지므로 \(n^n\)에 \(3 \times 1000\)개의 2가 나타나므로 이 경우도 제외할 수 있다. 최종 후보로는 \(n = 750, 1250, 1750\)의 셋이 남는다.

만약 \(n=750\)이라면, \(m^m\)의 소인수분해에는 \(2018-750=1268\)개의 2가 나타나야 한다. 그런데 \(2^2 \,\|\,1268\)이므로 1268을 나누는 \(r \times 2^r\)은 존재하지 않는다.

만약 \(n=1250\)이라면, \(2018-1250=768\)을 고려해야 하고, \(2^8 \,\|\, 768\)이므로 이 경우에도 768을 나누는 \(r \times 2^r\)은 존재하지 않는다. \(n=1750\)인 경우에도, \(2018-1750=268\)이 4로 나누어지지만 8로는 나누어지지 않으므로 마찬가지로 268을 나누는 \(r \times 2^r\)이 존재하지 않는다.

이상의 결과를 종합하면, \(m\)과 \(n\)의 곱이 가장 작은 경우는 \(m=56\)이고 \(n=1850\)일 때이다.

마지막 2018 자리가 0이고 끝에서 2019번째 자리가 0이 아니라면 m을 m번 곱하고 n을 n번 곱한 수를 소인수분해하였을 때 2의 승수와 5의 승수 중 작은 값이 2018이 되어야 합니다. 이 조건에 m과 n을 100000 이하의 수로 제한하고, 위와 같이 간단하게 C언어 코드로 작성하여 프로그램을 돌리면 (m, n) = (56, 1850) or (1850, 56)일 때 m과 n의 곱이 가장 작은 경우임을 알 수 있습니다.

그리고 m을 m번 곱하고 n을 n번 곱한 수의 2의 승수는 2의 배수이고 5의 승수는 5의 배수이기 때문에 이들 중 작은 값은 무조건 2의 배수이거나 5의 배수여야 합니다. 하지만 2019는 2의 배수도 아니고 5의 배수도 아니기 때문에 마지막 2019 자리가 모두 0이 되는 경우는 존재하지 않습니다.