Maths Olympiad Prep

Library / /280 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Question 5 Let the set S={1,2,,1000}S=\{1,2, \cdots, 1000\}. Now for any non-empty subset AA of SS, let αA\alpha_{\mathrm{A}} denote the sum of the largest and smallest numbers in AA, then, the arithmetic mean of all such αΔ\alpha_{\Delta} is \qquad

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is 1001.
Let S={1,2,,n},nNS=\{1,2, \cdots, n\}, n \in N. Let mA,MAm_{A}, M_{A} represent the minimum and maximum elements of a non-empty subset AA of SS, respectively. Then the arithmetic mean of all αA\alpha_{A} is
12n1ASA(mA+MA). \frac{1}{2^{n}-1} \sum_{\substack{A \subset S \\ A \neq \varnothing}}\left(m_{A}+M_{A}\right).

Since for 1kn1 \leqslant k \leqslant n, there are 2nk2^{n-k} subsets AA satisfying mA=km_{A}=k, we have
ASAmA=12n1+22n2++k2n1++n20. \begin{array}{l} \sum_{\substack{A \subset S \\ A \neq \infty}} m_{A}=1 \cdot 2^{n-1}+2 \cdot 2^{n-2}+\cdots+ \\ k \cdot 2^{n-1}+\cdots+n \cdot 2^{0}. \end{array}

And for 1kn1 \leqslant k \leqslant n, there are 2k12^{k-1} subsets AA such that MA=kM_{A}=k, hence
AMA=n2n1+(n1)2n2++(nk+1)2nk++120.(3) \begin{array}{l} \sum_{\substack{A}} M_{A}=n \cdot 2^{n-1}+(n-1) 2^{n-2}+\cdots \\ \quad+(n-k+1) 2^{n-k}+\cdots+1 \cdot 2^{0}.(3) \end{array}
Adding (2) and (3) gives
AS(mA+MA)=(n+1)(2n1+2n2A++2+1)=(n+1)(2n1). \begin{array}{l} \sum_{A \subseteq S}\left(m_{A}+M_{A}\right)=(n+1)\left(2^{n-1}+2^{n-2}\right. \\ A \neq \varnothing \\ +\cdots+2+1)=(n+1)\left(2^{n}-1\right). \end{array}

Combining (1), we know that the arithmetic mean of all such αA\alpha_{A} is n+1n+1.
From (2), we get
2ASmA=2n+22n1+A+(t+1)2nI++n2. \begin{array}{l} 2 \sum_{A \subset S} m_{A}=2^{n}+2 \cdot 2^{n-1}+\cdots \\ A \neq \varnothing \\ \quad+(t+1) 2^{n-I}+\cdots+n \cdot 2. \end{array}
Subtracting (2) from (A), we get
ASnA=2n+2n1++2nx+2n=2u+1n2. \begin{aligned} \sum_{\substack{A \subset S}}^{n_{A} \neq \varnothing} & =2^{n}+2^{n-1}+\cdots+2^{n-x}+2-n \\ & =2^{u+1}-n-2. \end{aligned}

Similarly, we have
ASAM=(n1)2n+1 \sum_{\substack{A \subset S \\ A \neq \varnothing}} M_{\triangle}=(n-1) 2^{\mathbb{n}}+1

Finally, let 1i<in1 \leqslant i<i \leqslant n, then the number of subsets ASA \subset S with ii and 11 as the minimum and maximum elements, respectively, is 2i112^{i-1-1}, and in this case, αA=i+j\alpha_{A}=i+j. Noting that α{1}=2i,1in\alpha_{\{1\}}=2 i, 1 \leqslant i \leqslant n. Therefore, we have the identity
21=1ni+1i<jn(i+j)2i11=(n+1)(2n1), \begin{array}{l} \mathbf{2} \sum_{\mathbf{1}=1}^{\mathbf{n}} i+\sum_{1 \leqslant \mathrm{i}<\mathbf{j} \leqslant \mathbf{n}}(i+j) 2^{i-1-1} \\ =(n+1) \cdot\left(2^{\mathbf{n}}-1\right), \end{array}

or 1i<j=n(i+1)2j1=2(n+1)(2nn1)\sum_{1 \leqslant \mathrm{i}<\mathrm{j}=\mathrm{n}}(i+1) 2^{\mathrm{j}-1}=2(n+1)\left(2^{\mathrm{n}}-n-1\right) (8)

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.