퀴즈 480 10 자리 수를 찾아라
다음 조건을 만족하는 10자리 수를 찾아라.
- 이 10자리 수는 0-9 를 모두 사용한다.
- 처음 n 개의 수를 독립적인 수라 생각하면 n 으로 나누어 떨어진다. e.g 예를 들어 5자리수 (abcde) 를 생각하면
처음 수(a) 는 1 의 배수 두번재 수(ab)는 2의 배수 3번째 수(abc)는 3의 배수 4번째 수(abcd)는 4의 배수 5번째 수 (abcde) 는 5의 배수라는 것을 의미한다.
풀이
이 문제를 푸는데 알아두면 좋은 지식이 있다. 바로 배수판정법 에 대한 내용이다.
해당 지식들이 이 문제를 푸는데 직접적으로 사용된다.
먼저 문제에 해당되는 조건을 나열해보자
자 먼저 짝수 자리까지의 수를 가지고 a_2, a_4, a_6, a_8, a_10 의 특징을 알아보자.
(i) 먼저 a_{10} 은 10의 배수이니까 a_{10}=0 임을 알 수 있고, a_{2}, a_{4}, a_{6}, a_{8} 은 짝수라는 것만 알 수 있다. 가능한숫자는 2,4,6,8 4개]
(ii) a_{5} 는 5의 배수인데, 0이 a_{10} 에 쓰였으니 a_{5}=5 밖에 해당되지 않는다.
(iii) 자 a_3, a_6, a_9 에 대해 알아보자.
여기서 a_5 = 5 니까 (a_4,a_6) 은 (2,8), (8,2), (4,6),(6,4) 중 하나 일 것이다.
a_3 a_4 가 4의 배수가 되려는데 a_3 가 홀수이니까 a_4 는 2 또는 6 밖에 되지 않는다. 즉 (a_4, a_6) 은 (2,8) 혹은 (6,4) 만 가능하다.
자 이제 trial and error 를 해보자.
먼저 (2,8) 의 경우를 해보자.
4가지 숫자가 나오는데, 7412589630, 7412583690, 1472583690, 1472589630 이 4가지 숫자는 7번째 짜리 까지 했을 때 7로 나누어 떨어지지 않는다.
비슷한 방식으로 (6,4) 에 대해 수행해보면 가능한 열자리의 숫자는 3816547290 이라는 것을 알 수 있다.
c.f) 사실 이 문제는 손으로 풀어도 되겠지만 코딩으로 충분히 해볼만한 문제이다. 간단한 코딩으로도 같은 답을 구할 수 있다.