Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 6.0 AIME, harder Prove it Brazil

For any non-empty subset AA of {1,2,,n}\{1, 2, \dots, n\} define f(A)f(A) as the largest element of AA minus the smallest element of AA. Find f(A)\sum f(A) where the sum is taken over all non-empty subsets of {1,2,,n}\{1, 2, \dots, n\}.

Solution

Let mm and MM be the sum of the minima and maxima of all subsets. Since the diameter of a set is the difference between its maximum and its minimum, the desired sum is MmM - m. We may include unitary subsets, since their minima and maxima coincide.

The number kk, 1kn1 \le k \le n, is the minimum of all subsets of the form {k}A\{k\} \cup A, where A{k+1,k+2,,n}A \subset \{k+1, k+2, \dots, n\}. So kk is the minimum of 2nk2^{n-k} subsets. Hence
m=k=1nk2nk=k=0n1(nk)2k. m = \sum_{k=1}^{n} k \cdot 2^{n-k} = \sum_{k=0}^{n-1} (n-k) \cdot 2^k.
Now we count the number of subsets with diameter kk. Let aa be the minimum of a subset. The maximum is a+ka+k. Since a+kna+k \le n, one may choose aa in nkn-k ways. Since there are k1k-1 numbers between aa and a+ka+k, there are (nk)2k1(n-k) \cdot 2^{k-1} subsets with diameters kk. Since there are 2nn12^n-n-1 non-empty and non-unitary subsets,
k=1n1(nk)2k1=2nn1    k=1n1(nk)2k=2n+12n2    k=0n1(nk)2k=2n+12n2+n=2n+1n2 \begin{align*} \sum_{k=1}^{n-1} (n-k) \cdot 2^{k-1} &= 2^n - n - 1 \\ \iff \sum_{k=1}^{n-1} (n-k) \cdot 2^k &= 2^{n+1} - 2n - 2 \\ \iff \sum_{k=0}^{n-1} (n-k) \cdot 2^k &= 2^{n+1} - 2n - 2 + n = 2^{n+1} - n - 2 \end{align*}
and m=2n+1n2m = 2^{n+1} - n - 2.

In order to compute MM, notice that the association A={a1,a2,,am}f(A)={n+1a1,n+1a2,,n+1am}A = \{a_1, a_2, \dots, a_m\} \to f(A) = \{n+1-a_1, n+1-a_2, \dots, n+1-a_m\} is clearly a bijection that transform minima \ell in maxima n+1n+1-\ell. Since there are 2n12^n-1 non-empty subsets, M+m=(n+1)(2n1)    Mm=(n+1)(2n1)2(2n+1n2)=(n3)2n+n+3M+m = (n+1)(2^n-1) \iff M-m = (n+1)(2^n-1)-2(2^{n+1}-n-2) = (n-3) \cdot 2^n + n + 3.

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 and solution reproduced as published; topic and difficulty added by this site.