Subset Sums in Order

★ 9/10combinatorics Statistics Counting Induction inequality

Problem

Let $a_1, a_2, \ldots, a_n$ be a strictly increasing sequence of positive integers. The set $\{a_1, a_2, \ldots, a_n\}$ has $2^n$ subsets, whose element sums (with the empty set counting as $0$ ) are $S_1, S_2, \ldots, S_{2^n}$ , and it is given that

S_1 < S_2 < \cdots < S_{2^n}.

1. Find the minimum possible value of $S_{2^n}$ . 2. Find the minimum possible variance of $S_1, S_2, \ldots, S_{2^n}$ . 3. Prove that

a_1^2 + a_2^2 + \cdots + a_n^2 \geqslant \frac{4^n - 1}{3}.

Answer

Solution

Difficulty	9/10
Topics	combinatorics, Statistics, Counting, Induction, inequality

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments

No comments yet.