Maths Olympiad Prep

Library / /3 of 11

Combinatorics Difficulty 5.0 AIME, harder Prove it Philippines

Problem:
Let v(X)v(X) be the sum of elements of a nonempty finite set XX, where XX is a set of numbers. Calculate the sum of all numbers v(X)v(X) where XX ranges over all nonempty subsets of the set {1,2,3,,16}\{1,2,3, \ldots, 16\}.

Solution

Solution:
The answer is 2158172^{15} \cdot 8 \cdot 17

We note that each k{1,2,3,,16}k \in \{1,2,3, \ldots, 16\} belongs to 2152^{15} subsets of {1,2,3,,16}\{1,2,3, \ldots, 16\}. We reason as follows: we can assign 0 or 1 to kk according to whether it is not or in a subset of {1,2,3,,16}\{1,2,3, \ldots, 16\}. As there are 2 choices for a fixed kk, kk belongs to half of the total number of subsets, which is 2162^{16}. Hence the sum is
v(X)=215(1+2+3++16)=215817=4456448 \sum v(X) = 2^{15}(1+2+3+\cdots+16) = 2^{15} \cdot 8 \cdot 17 = 4456448

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.