Let $S$ be the set $\{1, 2, ..., 10\}$. Let $A$ be a subset of $S$. We arrange the elements of $A$ in increasing order, that is, $A = \{a_1, a_2, ...., a_k\}$ with $a_1 < a_2 < ... < a_k$. Define WSUM for this subset as $3(a_1 + a_3 +..) + 2(a_2 + a_4 +...)$ where the first term contains the odd numbered terms and the second the even numbered terms. (For example, if $A = \{2, 5, 7, 8\}$, WSUM is $3(2 + 7) + 2(5 + 8)$.) Find the sum of WSUMs over all the subsets of S. (Assume that WSUM for the null set is $0$.)
Problem
Source: CRMO 2012 region 5 p6 Mumbai
Tags: Subsets, set theory, combinatorics, Combinatorics of set
aops29
04.06.2019 20:21
Hopefully this is correct? Seems a tad bit too hard for something like RMO.
The answer is \(2^7 \cdot 552\). We prove the more general formula \(2^{n-3}(5n^2 + 5n + 2)\), replacing the \(10\) with \(n\geq 3\).
Let \(f(X)\) denote the sum of all elements of the set \(X\), and let \(g(X)\) denote the sum
\(a_1 + a_3 + a_5 + \cdots\), where \(X=\{a_1,a_2,a_3,\ldots\}\) is arranged in increasing order.
Then what we want is
\[2\left(\sum_{X\subseteq [n]} f(X)\right) + \left(\sum_{X\subseteq [n]} g(X)\right)\]
First we calculate the first sum. To do this, note that in the sum, each number \(a\in[n]\)
is added exactly \(2^{n-1}\) times; it is added once for each subset, and there are
\(2^{n-1}\) such subsets (\(2\) options for each of the other \(n-1\) numbers). Thus, this sum
evaluates to
\[\sum_{a=1}^n 2^{n-1}\cdot a = n(n+1)\cdot 2^{n-2}\]and multiplying by \(2\) gives us the first part, which is \(n(n+1)\cdot 2^{n-1}\).
Now for the second sum (which is the meat of this solution):
\[\sum_{X\subseteq [n]} g(X)\]
To evaluate this, we again count how many times each \(a\in[n]\) is summed.
Suppose \(a=1\). Then, obviously, it is added \(2^{n-1}\) times in the sum. Now assume that
\(a\geq 2\). The number of subsets such that \(a\) is at the \((2k+1)\)-th position is
\[2^{n-a}\cdot \binom{a-1}{2k}\]where \(2^{n-a}\) is the number of ways to add elements greater than \(a\) to the subset, and
\(\binom{a-1}{2k}\) is the number of ways to choose the first \(2k\) elements of the set.
Thus, the second sum is
\[2^{n-1} + \sum_{a=2}^{n} \sum_{k=0}^{\infty} a\binom{a-1}{2k}\cdot 2^{n-a}\](this is obviously finite assuming \(\binom{n}{k} = 0\) for \(n<k\))
We can sum this as
\begin{align*}
\sum_{a=2}^{n} \sum_{k=0}^{\infty} a\binom{a-1}{2k}\cdot 2^{n-a} &= \sum_{a=2}^{n} a2^{n-a} \left(\sum_{k=0}^{\infty} \binom{a-1}{2k}\right) \\
&= \sum_{a=2}^{n} a\cdot 2^{n-a} \cdot 2^{a-2} \\
&= 2^{n-2} \sum_{a=2}^n a \\
&= n(n+1)2^{n-3} - 2^{n-2} \\
\end{align*}
and adding the \(2^{n-1}\) from before (the case \(a=1\)) gives us the expression
\[n(n+1)2^{n-3} + 2^{n-2}\]
Thus, our answer must be
\[n(n+1)2^{n-1} + n(n+1)2^{n-3} + 2^{n-2}\]which does indeed equal
\[2^{n-3} (5n^2 + 5n + 2)\]finishing the proof.
Now we can easily plug in \(n=10\) to find the answer to the original question.
NikoIsLife
05.06.2019 12:12
Let's solve a more general form, where $S=\{1,2,...,n\}$.
For some functions $f$ and $g$, define the WUMBO of a subset $A$ as $f(a_1)+g(a_2)+f(a_3)+g(a_4)+\cdots$. We can get the WSUM of the subset $A$ by setting $f(m)=3m$ and $g(m)=2m$.
Now, let $T$ be the sum of all the WUMBOs over all subsets of $S$.
Consider one element of the set, let's say $m>1$.
The number of ways for $m$ to appear as the oddth term of a subset $A$ is equal to number of subsets from $\{1,2,...,m-1\}$ which has an even number of elements, times the number of subsets $\{m+1,m+2,\ldots,n\}$ has. This is just equal to $2^{m-2}\cdot2^{n-m}=2^{n-2}$. This means, the number of times the term $f(m)$ appears in $T$ is equal to $2^{n-2}$.
The number of ways for $m$ to appear as the eventh term of a subset $A$ is equal to number of subsets from $\{1,2,...,m-1\}$ which has an odd number of elements, times the number of subsets $\{m+1,m+2,\ldots,n\}$ has. This is just equal to $2^{m-2}\cdot2^{n-m}=2^{n-2}$ as well. This means, the number of times the term $g(m)$ appears in $T$ is equal to $2^{n-2}$.
Now, $1$ is an exception, as it always appears as the first term of a subset $A$. This means, the term $f(1)$ appears $2^{n-1}$ times in $T$, but $g(1)$ never appears.
Therefore, the sum of the WUMBOs of all the subsets of $S$ is given by:
$T=2^{n-1}f(1)+\sum_{m=2}^n2^{n-2}(f(m)+g(m))$
And finally, since we're finding the sum of WSUMs over all subsets of $S$, we set $f(m)=3m$ and $g(m)=2m$ to get:
$2^{n-1}\cdot3\cdot1+\sum_{m=2}^n2^{n-2}(3m+2m)=2^{n-1}\cdot3+2^{n-2}\sum_{m=2}^n5m=\boxed{2^{n-3}(5n^2+5n+2)}$
which is the same formula as Aops29 had.
yrt
06.06.2019 16:22
Another solution by using sequence. calculate $F_n$ by Fn-1 i get a same answer