2017학년도 가톨릭대학교 논술 문제 중

2017학년도 가톨릭대학교 논술 문제 중에 divisor function에 대한 문제가 나왔다고 한다. 대략 다음과 같은 형태였다고 한다.

d(n)은 n의 약수의 개수이다. (단, n은 자연수)

\displaystyle a_n = \frac{1}{n}\sum_{k=1}^{n}d(k) 이라 정의하자.

[논제 1]
a_M = 3을 만족하는 M의 값을 구하고, n > M일 때 a_n >3인 사실을 설명하시오.

숫자 맞추기 수능만 열라게 파는 고교생들의 상당수는 정수론 문제를 풀 수 없을 것이라 생각하기 때문에, 상당수의 학생이 당황하지 않았을까 생각한다. ㅋㅋㅋ

Apostol 책[1;p57]에는 일전에 소개한 hyperbola method[2]를 이용하여, Divisor summatory function의 asymptotic size가 x log x임을 보이는 부분이 있다. 즉,

\displaystyle \sum_{n \le x} d(n) = x \log x + (2\gamma -1)x + O(\sqrt{x})

여기서 \gammaEuler–Mascheroni constant이다.

참고로 마지막의 O(\sqrt{x})을 improve하는 문제를 Dirichlet’s divisor problem이라고 하는데, 에러텀을 O(x^{\theta+\epsilon})이라고 둘 때, 모든 \epsilon >0에 대해 참인 가장 작은 \theta의 값을 찾는 문제는 아직 해결되지 않았다고 한다. 위키피디아의 Divisor summatory function 항목에 따르면, 현재까지 가장 좋은 결과[3]는 2003년에 나온 \inf \theta \le 131/416 이라고 한다.

여하간 이 사실을 이용하면 비교적 자명한 결과이긴 한데, 닭 잡는 데 소 잡는 칼을 쓰는 것 같아서 좀 그렇다. ㅋㅋㅋ 좀 더 고교생스러운 방법이 있을지 좀 생각해 봤다.

 


일단 노가다로-_- 정답이 M=15 임을 알 수 있다. M=18까지 계산하면 3M과 \sum d(n)의 차가 4 이상 벌어진다. 18 이후의 자연수를 세 개 단위로 그룹을 만들어보자. 각 그룹에는 반드시 2의 배수와 3의 배수가 포함된다.

그룹 안에서 2의 배수와 3의 배수가 다를 경우
2X의 경우 1, 2, X, 2X 로 약수가 적어도 네 개 이상, 3X의 경우도 1, 3, X, 3X으로 그룹 전체 약수의 총 개수는 (남은 한 수가 소수라고 해도) 적어도 2+4+4=10 이상이 된다. 따라서 3M과 \sum d(n)의 차는 더 벌어진다.

그룹 안에서 2의 배수와 3의 배수가 겹칠 경우
6X의 경우 1, 2, 3, 6, X, 2X, 3X, 6X로 여덟 개가 나온다. 따라서 약수의 총 개수는 2+2+8=12 이상이 되므로 3M과 \sum d(n)의 차는 더 벌어진다.

따라서 3M과 \sum d(n)의 차가 4 이상 벌어지면, 각 그룹안에 소수가 두 개 들어 있는 경우가 나타나도 역전되지 않는다.

 


[1] Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, MR0434929, ISBN 978-0-387-90163-3
[2] 내 백과사전 Dirichlet’s hyperbola method 2010년 10월 27일
[3] Huxley, M. N. (2003). “Exponential sums and lattice points III”. Proc. London Math. Soc. 87 (3): 591–609. doi:10.1112/S0024611503014485

Advertisements

2 thoughts on “2017학년도 가톨릭대학교 논술 문제 중

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중