Competition problem — Combinatorics

Library / /60 of 94

Combinatorics Difficulty 5.0 AIME Prove it United States

Problem:

For any finite set $S$ , let $f(S)$ be the sum of the elements of $S$ (if $S$ is empty then $f(S)=0$ ). Find the sum over all subsets $E$ of $S$ of $\frac{f(E)}{f(S)}$ for $S=\{1,2, \ldots, 1999\}$ .

Solution

Solution:

An $n$ element set has $2^{n}$ subsets, so each element of $S$ appears in $2^{1998}$ subsets $E$ , so our sum is $2^{1998} \cdot \frac{1+2+\ldots+1999}{1+2+\ldots+1999} = 2^{1998}$ .

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.