7월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!
7월의 퍼즐에 참여해주신 분 중 정답과 함께 좋은 풀이를 보내주신 이시우님께
HORIZON에서 준비한 선물을 전달드릴 예정입니다.
7이 일곱 개 있는 가장 큰 77자리 수는 9를 70개 나열하고 뒤에 7 일곱 개를 붙인 수이다. 만약 이 수가 7의 배수라면 9를 70개 나열한 수가 7의 배수가 되어야 한다. 그런데,
\[
\underbrace{99\dots9}_{70\text{개}} = 10^{70}-1
\]
이고, \(10, 10^2, 10^3, \dots\)을 7로 나눈 나머지가
\[
3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, \dots
\]
로 반복되므로, \(10^{70} = (10^6)^{11} \times 10^4\)를 7로 나눈 나머지는 \(10^4\)을 7로 나눈 나머지인 4와 같다. 따라서 9를 70개 나열한 수를 7로 나눈 나머지는 \(4-1=3\)이 된다. 그러면 우선
\[
\underbrace{99\dots9}_{69\text{개}}67777777
\]
은 7의 배수가 된다.
이 수보다 큰 7의 배수를 만들려면, 적당한 7의 배수를 더하여 6을 7로 바꾸고 7 하나는 다른 수로 바꾸어야 한다. 먼저 \(67+7 = 74\)를 이용하면
\[
\underbrace{99\dots9}_{69\text{개}}74777777
\]
이 7의 배수가 된다. 같은 식으로, 4를 7로 바꾸려면 \(47 + 28 = 75\)를 이용하여
\[
\underbrace{99\dots9}_{69\text{개}}77577777
\]
을 만들 수 있다.
이번에는 \(57+21 = 78\)을 이용하여
\[
\underbrace{99\dots9}_{69\text{개}}77787777
\]
을 만들 수 있다. 이 수는 7보다 큰 8을 사용하고 있으므로 8을 7로 바꾸거나 할 필요가 없다. 따라서 이 수가 문제의 조건에 부합하는 가장 큰 수가 된다.
다음은 7월의 정답자로 선정된 이시우님의 해설입니다.
먼저 몇가지 간단한 사실을 짚고 넘어갑니다.
1. a, b가 모두 어떤 수 m의 배수이면 a, b를 그대로 이어서 쓴 수도 역시 m의 배수이다.
이는 이어서 쓴 수가 a * 10 ^ (b의 자리수) + b가 되기 때문입니다.
2. 999999 = 7 * 142857은 7의 배수입니다.
되도록이면 큰 수를 만들기 위해서 앞에 최대한 많은 수의 9를 배치해야합니다. 위의 1, 2에 의해 99…99 (9가 66개)는 7의 배수이고, 따라서 99…9900…00 (9가 66개, 0이 11개) 역시 7의 배수입니다. 이제 0 대신 7개의 7과 다른 숫자들을 이용하여 최대한 큰 숫자를 만들면 됩니다.
7 일곱개가 가장 마지막에 온다고 가정하면, 66개의 9와 7개의 7 사이 네자리 역시 7의 배수가 되어야 하고, 가장 큰 네자리 7의 배수는 9996임을 손으로 계산할 수 있습니다. (10000을 7로 나눠보면 됩니다.) 따라서
999999 … 999999 9996 7777777
은 7의 배수가 됩니다. 이보다 더 큰 숫자가 존재한다면 9996 대신에 9997, 9998, 혹은 9999가 나와야하고, 9998이나 9999인 경우 문제의 조건에 의해서 남은 7자리는 모두 7이 되어야 합니다. 하지만 이는 9998, 9999가 7의 배수가 아니기 때문에 불가능합니다.
9997이 가능하다면 마지막 7자리는 6개의 7과 다른 숫자 하나로 이루어져 있을텐데, 다른 숫자가 들어갈 위치가 정해지면 7의 배수라는 조건에 의해서 어떤 숫자가 들어가야하는지 계산할 수 있습니다. 예를 들어서 마지막 11자리가
9997_777777
이라면 99967777777이 7의 배수이기 때문에 둘의 차이인 (7_ – 67) * 10^6도 7의 배수가 되어야 하고, 빈칸에는 4가 들어가야 함을 알 수 있습니다. 마찬가지로
99977_77777
의 경우에 앞에서 구한 99974777777을 이용하면 5가 적절한 숫자임을 알 수 있습니다. 이를 나머지 빈칸 위치에 대해서 반복해 보았을 때, 7보다 큰 숫자가 나오는 경우 그 때의 숫자가 가능한 가장 큰 숫자가 됩니다. 실제로 한단계만 더 계산해보면
99977787777
이 7의 배수가 되고, 따라서 문제의 조건을 만족하는 가장 큰 숫자는
999…99977787777 (9가 69개)
가 됩니다.
