Q. 어떤 복도에 락커가 100개 있고, 모두 문이 닫혀있다고 해보자.그 복도를 지나가면서 처음에는 100개의 락커 문을 모두 연다. 그런 후 짝수 번째 락커를 모두 닫는다. 다시 이번에는 3의 배수 번째 락커가 열려 있으면 닫고 닫혀있으면 연다.(이 과정을 토글이라 하자) 복도를 100번 지나고 나면 열려있는 락커는 총 몇 개일까?
.
.
.
.
.
.
.
.
.
.
.
A. 10번째 락커를 생각해보자.
10번 락커는 몇 번째 지나갈 때 토글될까?
우선 첫 번째를 지나갈 때는 모든 락커를 토글하니 당연히 토글되고, 10번 째 지나갈 때도 토글 될 것이다.
이제 두 번째부터 9번째까지를 살펴봐야하는데, 두 번째를 지나갈 때는 2, 4, 6, 8, 10번째 락커를 토글하고 세 번째는 3, 6, 9 네 번째는 4, 8 다섯 번째는 5, 10번을 토글하게 된다. 이런식으로 확인 하다보면 10의 약수번째를 지나갈 때만 락커를 토글하는 것을 알 수 있다. 조금 더 생각해보자면 n번째 지나갈 때 10번 락커를 토글하려면 n의 배수 중에 10이 있어야 한다. 즉 n은 10의 약수여야한다.
10의 약수에는 1, 2, 5, 10이 있다. 각각의 경우 문을 열고 닫고, 열고 닫는다.
따라서 약수의 개수가 짝수이면 락커가 닫혀있다.
약수의 개수가 홀수라면 반대로 락커가 열려있을 것이다.
그렇다면 약수가 홀수개이기 위한 조건은 어떤 것일까?
같은 수를 곱해야 하는 수가 약수에 속한다면 홀수를 가질 수 있다.
이를 '완전제곱수'라 한다. 따라서 n은 '완전제곱수'여야 한다.
결론은 1이상 100이하의 완전제곱수는 1, 4, 9, 16, 25, 36, 49, 64, 81, 100이라 할 수 있다.
총 10개의 락커가 열려 있을 것이라는 판단이다.