배수판정법 응용 문제

Q. 자연수가 주어졌을 때 각 자리 수의 합을 구하는 시행을 생각하자. 111111111111^11111111111에서 시작해 시행을 반복했을 때 최종 결과인 한 자리 수는 얼마인가? 

 

제목에서 크나큰 힌트를 제공해버렸다. 

이 문제는 콴다 선생님으로 문제 좀 풀어주다가 발견한 문제를 조금 변형한 것이다.

tmi지만 콴다에서 한 70문제 풀고 4만원 조금 넘게 벌었다. 최저 시급이 안 되는 것 같지만(문제가 바로 존재하는 것이 아니라서 새로고침을 계속 해야 한다), 나는 한 문제 당 100원 기부 가능한 지식인 등급도 초인일 정도로 문제 풀어주는 걸 나름 좋아하기 때문에 계속 하고 있다. 아직 만 나이가 안 돼서 지식인 교육봉사를 못하는데, 생일 지나면 지식인으로 넘어갈 것이다. 

어쨌든 문제를 풀어보자.

sol) 상식적으로 저 자연수를 구할 수 없다. 노가다가 안 된다는 뜻이다.

그러면 아이디어는 '각 시행에서 변하지 않는 특징'을 찾는 것이다. 조합에서는 불변량이라고 하던가? 

그리고 최종 결과가 한 자리 수라는 뜻은, 한 자리 수 중 그 특징을 가진 수는 하나 뿐이라는 뜻이다. 

그래서 고민을 해보면,

각 자리 수 합이라는 것이 어딘가 익숙하다. 언제 봤는가? 바로 3의 배수 판정법 또는 9의 배수 판정법에서 봤다.

9의 배수 판정법은 9의 배수인 것과 각 자리 수의 합이 9의 배수인 것이 필요충분임을 이용한 판정법이다. 

즉, 9의 배수라면, 시행한 결과도 9의 배수일 것이다!

(3의 배수는 한 자리 수 중 3의 배수가 유일하지 않으므로 9의 배수로 생각한다)

원래 주어진 수를 보자. 1이 12개인 수의 거듭제곱 꼴이다.

1이 12개인 수의 각 자리 합은 12이므로 3의 배수이다.

3의 배수를 거듭제곱하면 9의 배수이다.

따라서 원래 주어진 수는 9의 배수이다!

그러므로 시행을 계속 반복했을 때, 최종값은 9의 배수인 9이다.□

 

좀 더 엄밀히 하자면,

각 자리 수의 합이 0인 수는 0 뿐이므로 불가능하다.

또한 '시행'의 결과가 한 자리 수가 되는 것은,

두 자리 수 이상의 수의 각 자리 합을 구하면 원래 수보다 작아지기 때문이다. 

n>2일 때 n자리 수의 각 자리 수 합은 9n 이하인데, n자리 수는 10^(n-1) 이상이기 때문이다. 

두 자리 수는 각 자리 수 합은 18 이하고, 18 이하의 모든 두 자리 수의 각 자리 수 합을 구해보면 원래 수보다 작다. 

한 자리 수는 각 자리 수를 더해도 당연히 그 수다. 

 

그리고 꼭 9의 배수일 필요 없이, 시행 후 mod 9 값이 보존되기 때문에 임의의 수에 대해서도 결과를 얻을 수 있다.

아마 초등학교 경시 문제라 9의 배수로 값을 준 것 같다. 

 

나름 흥미로운 문제였다.