Competition problem — Combinatorics

Library / /77 of 264

Combinatorics Difficulty 5.3 AIME, harder Prove it Romania

Let $n$ be a strictly positive integer. For any natural number $k$ , we denote by $a(k)$ the number of natural divisors $d$ of $k$ such that $k \le d^2 \le n^2$ . Compute the sum $\sum_{k=1}^{n^2} a(k)$ .

Solution

$S(n) = \{(k, d) \mid d \text{ divides } k, k \le d^2 \le n^2, 1 \le k \le n^2\}.$
For $1 \le k \le n^2$ , let $A(k)$ be the set of the natural divisors $d$ of $k$ such that $k \le d^2 \le n^2$ .
A natural number $d \in \{1, 2, \dots, n\}$ belongs to the sets $A(d)$ , $A(2d)$ , $\dots$ , $A(d^2)$ and only to them.
It follows that the contribution of each $d$ in the sum $\sum_{k=1}^{n^2} a(k) = \sum_{k=1}^{n^2} |A(k)|$ is $\underbrace{1 + 1 + \dots + 1}_{d \text{ terms}} = d$ .
Thus, $\sum_{k=1}^{n^2} a(k) = \sum_{d=1}^{n} d = n(n+1)/2$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.