HMMT 二月 2004 · 团队赛 · 第 14 题
HMMT February 2004 — Team Round — Problem 14
题目详情
英文原题
- [30] Prove thatσ (1) + σ (2) + σ (3) + · · · + σ ( n ) ≤ n 2
for every positive integer n .
解析
英文解析
- Prove thatσ (1) + σ (2) + σ (3) + · · · + σ ( n ) ≤ n 2
for every positive integer n .
Solution: The i th term on the left is the sum of all d dividing i . If we write this sumout explicitly, then each term d = 1 , 2 , . . . , n appears b n/d c times — once for eachmultiple of d that is ≤ n . Thus, the sum equalsb n/ 1 c + 2 b n/ 2 c + 3 b n/ 3 c + · · · + n b n/n c ≤ n/ 1 + 2 n/ 2 + 3 n/ 3 + · · · + n/n = n + n + · · · + n = n .2