간단한 수학문제.

luztain House 에서 본 문제..

"
어떤 학교의 복도에는 열려있는 1,000개의 창문이 있다. 학생 역시 1,000명이 있다.

자 이제 학생들이 삽질을 시작한다.
닫혀있는 창문은 열고, 열려있는 창문은 닫고 간다.

1번째 학생은 열려있는 모든 창문을 닫고 간다.

2번째 학생은 2의 배수의 창문을 모두 건드린다.
3번째 학생은 3의 배수의 창문을 모두 건드린다.
…………
1000번째 학생은 1000의 배수의 창문을 모두 건드린다.



Q. 열려있는 창문의 갯수는?
"


요약하자면, N이란 숫자가 짝수개의 약수를 가지면 문이 열려있다는 얘깁니다마나는.

먼저 소수부터 생각해 보죠.

소수는 1과 자신 이외에는 약수를 가지지 않는 수 입니다.
따라서 2개의 약수를 가지죠.

여기서부터 문제를 풀어갑시다.

문제는 합성수 인데,
합성수는 소수의 곱으로 이루어 지지요.

합성수는 a^n + b^m + c^l ... z^r 로 이루어 지고, a,b,c 는 모두 소수입니다.
그리고 약수의 갯수 = (n+1)*(m+1)*...*(r*1)입니다.
해당사항은 아마 중학교 or 초등학교 약수의 갯수~ 시간에 배우는 공식인걸로 압니다.

...
(굳이 해당 공식에 대해 유도를 하자면,
a가 n회 존재할 경우의 수 + a^0=1 인 경우의 수에 각각의 경우의 수를 전부 곱하는 겁니다)

...
홀수 * 홀수 = 홀수 <- 창문이 닫혀 있음
짝수 * 짝수 = 짝수 <- 창문이 열려 있음
짝수 * 홀수 = 짝수 <- 창문이 열려 있음

이므로

n+1, m+1, r+1....은 모두 홀수여야 창문이 닫혀있는 형태가 되구요.
따라서 n,m,r은 모두 짝수 여야 합니다. (0 포함)

n.m,r...이 모두 짝수일려면,
동일한 수를 두번 곱하는 것이므로 제곱수 (1,4,9,16,25... )등이 있구요.

1000이하의 최대 제곱수는.. 31^31 = 931이니깐.

1000 - 31 = 969개가 열려있게 되겠군요.



...
아직 머리가 죽지 않았어~