다음, 2번 사람이 지나가면서 번호가 2의 배수(2, 4, 6, ...)인 문을 모두 닫는다.
그리고, 3번 사람이 지나가면서 번호가 3의 배수(3, 6, 9, ...)인 문을 열려있으면 닫고, 닫혀있으면 열어놓는다.
이렇게 각 번호의 사람은 자기 번호의 배수의 번호를 가진 문을 열려있으면 닫고, 닫혀있으면 열어놓는다고 한다. 100번째 사람까지 모두 문을 열고 닫았을 때, 열려있는 문은 모두 몇 개일까?
풀이
예를 들어 45번 문이 열려있는지 닫혀있는지 조사해보자.
45번 문을 손 댄 사람은 자기 번호가 45의 배수가 되는 번호를 가졌을 것이다. 세어보면 1번, 3번, 5번, 9번, 15번, 45번일 것이다. 이 번호들은 결국 45의 약수들이기 때문에 각 문의 여닫힘은 곧 약수의 개수를 찾는 일과도 같다.
45의 경우 약수가 6개였기때문에 문은 닫혀있을 것이다. 사실, 어떤 문이 열려있기 위애서는 45와 달리 약수의 개수가 홀수개여야 한다. 그렇다면 어떤 수들이 약수의 개수가 홀수개일까?
.
45의 약수가 짝수인 이유는 (1, 45), (3, 15), (5, 9) 이렇게 두 곱이 45가 되도록 짝지을 수 있기 때문이다. 그렇다면 제곱수는 어떨까? 가령 36의 경우 (1, 36), (2, 18), (3, 12), (4, 9) 로 짝짓고 나면 6이 홀로 남게 된다. 제곱수가 아닌 수는 모두 곱으로 짝지울 수 있기 때문에, 오직 제곱수만이 약수의 개수가 홀수가 된다.
따라서 열려있는 문은 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 이렇게 10개가 된다.
참고
보통 주어진 양의 정수 n에 대하여 n의 약수의 개수를 그리스어 τ(타우)를 써서 τ(n)으로 정의한다.
n이 1보다 크고, 그 소인수분해가 (p_1)^(k_1)*(p_2)^(k_2)*...*(p_r)^(k_r) 꼴일 때,
τ(n) = (1+k_1)(1+k_2)...(1+k_r)
이다.
이 공식에 따르면 약수의 개수 τ(n)가 홀수이려면 1+k_1부터 1+k_r까지 모두 홀수여야하므로 k_1부터 k_r까지 모두 짝수여야한다.
승수가 모두 짝수이면 n은 결국 제곱수가 된다.
또한, n이 제곱수가 아니라면 소인수분해에서 승수들 중 하나 이상이 홀수여야 하므로 1+k_1부터 1+k_r중 하나 이상이 짝수가 되고 그 모두의 곱인 τ(n)은 짝수가 된다.
