🔗

Let \(a_1, a_2, \dots, a_n\) be positive integers. Let \(b_k\) denote the number of those \(a_i\) for which \(a_i\) is greater than or equal to \(k\). Prove that \[ a_1 + a_2 + \cdots + a_n = b_1 + b_2 + \cdots + b_{a_n}. \]

🔗

Click here for the spoiler!

Try to interpret both sides of the equation in terms of counting objects.
Can you think of a way to represent the integers \(a_1, a_2, \ldots, a_n\) using dots?

🔗

Click here for the spoiler!

Consider the set \[ S = \{(i, j) : 1 \leq i \leq n, 1 \leq j \leq a_i\}. \] The size of this set is equal to \(a_1 + a_2 + \cdots + a_n\). On the other hand, for any positive integer \(j\), the number of \(i\) such that \((i, j) \in S\) is exactly \(b_j\). This shows that the size of \(S\) is also equal to \(b_1 + b_2 + \cdots + b_{a_n}\). This yields the desired result.

Alternatively, note that

\(\begin{align*} a_1 + a_2 + \cdots + a_n & = \sum_{i=1}^n \sum_{j=1}^{a_i} 1 \\ & = \sum_{i=1}^n \sum_{j=1}^{a_n} 1_{a_i \geq j}(i,j) \\ & = \sum_{j=1}^{a_n} \sum_{i=1}^n 1_{a_i \geq j}(i,j) \\ & = \sum_{j=1}^{a_n} b_j, \end{align*} \\)

where \(1_{a_i \geq j}(i,j)\) is \(1\) if \(a_i \geq j\), and \(0\) otherwise.

Lecture notes for Math Olympiad (IOQM, RMO, INMO)

Click on the icons below to download.

Topics Links

Algebra

Combinatorics

Geometry

Number Theory

INMO Training Camp

IMO Training Camp

MOPSS

Simon Marais Mathematics Competition

Resources