재미있는 수학문제

안녕하세요, 수학하는 아재입니다. 홀홀홀

예전에 어디서 본 재미있는 수학 문제인데 취미로 수학공부를 하시는 분들도 있을까 싶어서 나눠봅니다.

문제: 여기 방이 100개가 있습니다. 사람도 100명이 있지요. 각 사람과 방마다 1~100까지 번호가 부여됩니다. 

모든 방의 불은 꺼져있습니다. 스위치를 누르면 불이 켜지고, 한번 더 누르면 불이 꺼지는 구조입니다.

1번 사람은 모든 방의 전등 스위치를 누릅니다.

2번 사람은 2호실, 4호실, 6호실, … 등 2의 배수 호실 방에 들어가 전등 스위치를 누릅니다. 

3번 사람은 3호실, 6호실, 9호실 … 등 3의 배수 호실 방에 들어가 전등 스위치를 누릅니다.

4번 사람은 4의 배수 호실 방에, 5번 사람은 5의 배수 호실 방에, 이처럼 100번 사람까지 이 과정을 모두 반복했다고 가정합시다.

그렇다면 가장 마지막에 불이 켜져있는 방의 개수는 몇개일까요?

해설:

가장 처음에 방은 불이 꺼져있었습니다.

위 과정을 마친 후에 방에 불이 켜져있으려면 전등 스위치가 총 홀수번 눌려야 합니다. 1번, 3번, 5번 이렇게 말이지요.

다시말해 N호실의 불이 켜져있으려면, N호실에 들어가는 사람의 수가 총 홀수명이어야 된다는 뜻입니다.

그렇다면 N호실에 들어가는 사람의 수는 몇명일까요?

예컨대 N이 10이라면, N호실에 들어가는 사람은 1번, 2번, 5번, 10번입니다.

만약 N이 20이라면, 1번, 2번, 4번, 5번, 10번, 20번 사람이 들어갔겠지요.

즉 N호실에 입장하는 사람은 N을 나누는 수의 번호를 부여받은 사람입니다.

종합하자면, N호실에 불이 켜져있다 => N호실에 홀수명이 들어갔다. => N을 나누는 수, 이른바 N의 제수는 홀수개다 가 되겠습다.

d가 N의 제수라면 N/d 역시 N의 제수입니다. 예컨대 N이 40이고 d가 4면, d는 N을 나누죠. 동시에 N/d = 10 역시 N을 나눕니다.

그러므로 N의 제수들을 모두 모아보면 d와 N/d를 서로 짝지어줄 수 있습니다. 일반적인 경우에 N의 제수는 짝수개지요.

하지만, 만약 d와 N/d이 같은 경우에는 문제가 생깁니다. 즉 N = d^2이라면, 위와 같은 방법으로 제수들을 짝지어줄 시, 제 짝이 없는 제수 d가 존재하게 됩니다. 즉 N = d^2라면, N의 제수는 홀수개가 됩니다.

그러므로 d^2꼴의 호실의 방들은 마지막에 불이 켜져있는 상태가 됩니다.

1~100 중 제곱수는 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 총 10개가 있습니다. 그러므로 가장 마지막에 불이 켜져있는 방은 총 10개가 됩니다.