Competition problem — Combinatorics

Library / /17 of 23

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

On a given street, there are $n$ houses numbered from $1$ to $n$ . Let $a_{i}$ ( $1 \leq i \leq n$ ) be the number of people living in the house numbered $i$ , and let $b_{i}$ ( $i \geq 1$ ) be the number of houses on the street in which at least $i$ people live. Prove that
$a_{1}+a_{2}+\cdots+a_{n}=b_{1}+b_{2}+b_{3}+\cdots$

Solution

Solution:

Let us number the people in each house from $1$ up to the total number of people living there. Then for each $k \geq 1$ , the label $k$ is assigned as often as there is a house with $k$ or more people; thus there are $b_{k}$ people labeled $k$ . The quantity
$b_{1}+b_{2}+b_{3}+\cdots$
thus represents the total number of people labeled with some positive integer; this is the total number of people in all the houses, $a_{1}+\cdots+a_{n}$ .

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.