Insight Eyes

문제적 남자에서 수능 100일 전 특집으로 수능 만점자 3명을 게스트로 데려와 문제 풀기에 참여시켰네요. 참 대견한 친구들입니다. 서울대 의대, 경영대, 사회대에 진학한 친구들이라네요. 이 중 삼수한 친구는 제 직속 과후배라 더 반갑습니다.

각설하고, 오늘 답이 나오지 않은 문제... 이 문제 푸느라 고생하시는 분들이 꽤 많을 것 같아 글 써보고 있습니다. 저도 꽤 고생하여 답을 냈네요. 0부터 9까지 수로 10자리 숫자를 만들어내는 문제라 조합이 많아 어떻게 가능한 조합을 줄여갈지가 고민 시간의 대부분이었습니다.

먼저, 문제를 보면...

처음 보기에 참 막막합니다. 조합을 줄여나가는 절묘한 방법이 필요합니다.

여기서 조합을 줄일 수 있는 첫 번째 단서는 5의 배수와 10의 배수입니다. 5의 배수가 되는 숫자의 끝자리는 5와 0입니다. 그런데 10의 배수가 되는 수의 끝자리가 0이므로 둘이 공존하려면 10번째 자리는 0, 5번째 자리는 5여야 합니다.

그럼 숫자는 이렇게 되겠네요.
_ _ _ _ 5 _ _ _ _ 0

자, 이제는 생각을 좀 해봐야 합니다. 먼저 생각되는 건, 9번째 자리입니다. 9의 배수가 된다는 의미는 숫자의 각 자리 수의 합이 9의 배수라는 의미입니다.

그런데 지금 0부터 9까지의 수를 가지고 배열을 할 예정이므로 각 자리의 숫자의 합은 45입니다. 결국 어떤 배열을 해도 9의 배수가 된다는 의미죠. 그렇다면 9번째 자리는 남는 수를 아무 수나 넣어도 됩니다. 고민할 필요가 없는 자리네요.

그리고 조건을 통해 알 수 있는 또 하나의 전제조건... 바로 짝수 자리에는 무조건 짝수가 들어가야 하고 홀수 자리에는 홀수가 들어가야 한다는 사실입니다. 짝수 자리가 2, 4, 6, 8의 배수이니 당연히 그렇겠죠?

처음에는 저도 첫 자리에 1, 3, 7, 9(5는 썼으니까...)를 넣어 조합을 만들어 볼까 했습니다. 아무리 자릿수에 짝/홀이 정해져 있다고 하더라도 조합이 너무 많이 나옵니다. 그래서 다른 방법을 찾기로 했습니다. 조건에 맞는 가장 작은 조합을 만들어 낼 수 있는 방법을 찾기로 했죠.

생각해 본 결과, 6~8자리의 조합을 만들어 내는 게 가장 쉽다는 것을 알아냈습니다. 8자리까지는 8의 배수가 되어야 합니다. 그렇다면 1000이 8의 배수이니 6~8자리가 8의 배수이면 조건을 만족합니다. 다만, 0과 5는 사용되었으니 포함되면 안되고, 7번째 자리는 홀수여야 합니다.

가능한 조합은...
216
296
416
432
472
632
672
816
832
872

총 10개 조합이 나오네요.

이 조합 중 조건에 맞는 조합을 또 찾아봅니다. 이번에는 6의 배수의 특성을 이용하려 합니다. 6의 배수는 각 자리의 숫자의 합이 3의 배수이면서 짝수인 수입니다. 그리고 3번째 자리까지는 3의 배수이므로 1~3번째 자리의 각 자리 숫자의 합은 이미 3의 배수일 것입니다. 결국 4~6번째 자리의 각 자리의 숫자의 합이 3의 배수여야 합니다.

다음 단계까지 나가버리면 좀더 쉽게 구할 수 있겠다는 생각이 드네요. 3~4번째 자리는 4의 배수여야 합니다. 4의 배수의 특징이 끝 2개 자리가 4의 배수이니까요. 그런데 위의 조건들을 살펴보면 3번째 자리는 홀수여야겠죠?

그렇다면 위 조합에 3~5번째 자리를 추가해서 보면...

_ _ 5216 _ 0
_ _ 5296 _ 0
위 두 조합은 52의 각 자리 숫자 합이 7이므로 앞 자리가 2, 5, 8이 가능하지만 2, 5는 사용되었으니 8이 가능합니다. 그런데 3~4번째 자리가 4의 배수가 되려면 3번째 자리가 모두 짝수가 되니 둘 다 탈락입니다.

_ _ 5416 _ 0
_ _ 5432 _ 0
_ _ 5472 _ 0
위 두 조합은 54의 각 자리 숫자 합이 9이므로 앞 자리가 0, 3, 6, 9가 가능하지만 4번째 자리는 짝수여야 하니 6만 가능합니다. 그런데 첫번째 조합은 6이 쓰였으니 가능한 조합이 없습니다. 그래서 탈락... 두번째 조합에서는 3~4번째 자리가 4의 배수가 되려면 16, 76, 96이 가능하네요. 그래서 아래 조합이 살아남습니다.

a) _ _ 165432 _ 0
b) _ _ 765432 _ 0
c) _ _ 965432 _ 0

세번째 조합에서는 16, 36, 96이 가능하네요. 아래 조합도 살아남습니다.

d) _ _ 165472 _ 0
e) _ _ 365472 _ 0
f) _ _ 965472 _ 0

_ _ 5632 _ 0
_ _ 5672 _ 0
위 두 조합에서는 4번째 자리에 가능한 숫자가 4밖에 없고 3번째 자리에는 홀수로 가능한 숫자가 없네요. 둘 다 탈락...

_ _ 5816 _ 0
위 조합에서는 4번째 자리에 2가 가능하고, 3~4번째 수로 32, 72, 92가 가능합니다. 아래 조합이 살아남습니다.

g) _ _ 325816 _ 0
h) _ _ 725816 _ 0
i) _ _ 925816 _ 0

_ _ 5832 _ 0
_ _ 5872 _ 0
위 두 조합에서는 4번째 자리에 가능한 숫자가 2, 8이나 모두 이미 쓰였기에 가능한 숫자가 없습니다. 모두 탈락...

남은 조합은 다음과 같습니다.
a) _ _ 165432 _ 0
b) _ _ 765432 _ 0
c) _ _ 965432 _ 0
d) _ _ 165472 _ 0
e) _ _ 365472 _ 0
f) _ _ 965472 _ 0
g) _ _ 325816 _ 0
h) _ _ 725816 _ 0
i) _ _ 925816 _ 0

이제 사용하지 않은 숫자 중에서 2번째 자리에 짝수, 1~3번째 각 자리 숫자의 합이 3의 배수가 되도록 넣고 마지막 남은 숫자를 9번째 자리에 넣어서 조합을 만들어 냅니다.

g) h) i)는 위 조건을 만족할 수 있는 숫자를 만들 수 없네요. 최종적으로 가능한 조합은...

a) 9816543270
b) 9876543210
c) 1896543270
d) 3816547290
e) 1836547290
f) 1896547230

6개 조합이 남았습니다. 자, 이제 사용하지 않은 조건 한 가지가 남았습니다. 바로, 7번째 자리까지 7의 배수라는 조건입니다. 위 6개 수의 7번째 자리까지 잘라서 7로 나눠보면, 1개만 나눠지고 나머지는 나눠지지가 않네요.

바로…

d) 3816547290

이것이 우리가 찾는 답이었습니다.

저는 20분 만에 이렇게 풀었는데요... 머리 좋으신 분들은 훨씬 쉬운 방법으로 풀어내셨겠죠? 더 좋은 방법이 있다면 공유해 주세요~

도움이 되시길 바랍니다~ ^^