For any non-empty subset $X$ of $M=\{1,2,3,...,2021\}$, let $a_X$ be the sum of the greatest and smallest elements of $X$. Determine the arithmetic mean of all the values of $a_X$, as $X$ covers all the non-empty subsets of $M$.
Problem
Source:
Tags: number theory, Subsets, romania, Romanian TST
06.06.2021 19:22
For sake of brevity let $n = 2021$. For each $t \in M$ let us count how many sets $\mathcal S$ exist with the property that $\min_{y \in \mathcal S} y = t$. Assuming that we have done the counting of this and that of the analogous maximum case, let us see how we can evaluate the final answer. Indeed the answer is simply the sum of all products of $t$ with the number of times it may be the minimum(maximum) of a subset of $M$ where $t$ ranges over all elements in $M$. So let us count this great quantity that supposedly solves the problem. If we fix $t$ then the number of sets $\mathcal S$ with the minimum being $t$ is precisely $2^{n-t}$ since every element of $\mathcal S$ must be contained in $\{t, t+1, \cdots, n\}$ and $t \in \mathcal S$ must also be true. So this is one part of the count. The other part is where we evaluate the same sum but for the maximum. Simple inspection reveals that this count is $2^{t-1}$. So our sum is $$\sum_{t \in M} 2^{n-t}+2^{t-1}$$Evaluating this we get the grand total of $2(2^n-1)$. Thus the arithmetic mean is $2$, since the empty set was never counted.