Exercise 4.5.6* (Existence of two distinct subsets of $\mathscr{S}$ having equal sums of elements)

Question

Let $k$ and $n$ be integers satisfying $n>k>1$. Let $\mathscr{S}$ be any set of $k$ integers selected from $1,2,3,\ldots,n$. If $2^k >kn$, prove that there exist two distinct nonempty subsets of $\mathscr{S}$ having equal sums of elements.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} \begin{proof} We suppose that $2^k >kn$. We define, for all $A \in \mathscr{P}(\mathscr{S})$, $$S_A = \sum_{a \in A} a,$$ and $$S = \sum_{A \in \mathscr{P}(\mathscr{S})} S_A.$$ Note that $S_\varnothing = 0$, so that $S = \sum\limits_{A \in \mathscr{P}(\mathscr{S}) \setminus \{\varnothing\}} S_A$. \medskip Let us give a rough upper bound for $S$ (but not too rough: the obvious inequality $S < 2^k k n$ is not sufficient). Here $\mathscr{P}_i(\mathscr{S})$ is the set of subsets of $\mathscr{S}$ with $i$ elements. If $A \in \mathscr{P}_i(\mathscr{S})$, where $1 \leq i \leq k$, then \begin{align*} S_A &= \sum_{a \in A} a \ &\leq n + (n-1) + (n-2) + \cdots + (n - i + 1)\ &= i \, \frac{2n + 1 - i}{2}. \end{align*} We obtain, using $ i \binom{k}{i} = k \binom{k-1}{i-1} \ ( ext{if } i \geq 1)$ and $i(i-1) \binom{k}{i} = k(k-1) \binom{k-2}{i-2}\ \ ( ext{if } i \geq 2)$, \begin{align*} S &= \sum_{A \in \mathscr{P}(\mathscr{S}) } S_A \ &=\sum_{i = 1}^k \sum_{A \in \mathscr{P}_i(\mathscr{S}) } S_A\ &=\sum_{i = 1}^k \binom{k}{i} i \, \frac{2n + 1 - i}{2}\ &= n \sum_{i=1}^k i \binom{k}{i} - \frac{1}{2} \sum_{i = 2}^k i(i-1) \binom{k}{i}\ &= nk \sum_{i = 1}^k \binom{k-1}{i-1} - \frac{k(k-1)}{2} \sum_{i = 2}^k \binom{k-2}{i-2}\ &= nk 2^{k-1} - \frac{k(k-1)}{2} 2^{k-2}\ &< n k 2^{k-1} & ( ext{since } k>1), \end{align*} so \begin{align} S < 2^{k-1}n k . \end{align} Now assume for the sake of contradiction that there don't exist two distinct nonempty subsets of $\mathscr{S}$ having equal sums of elements. The minimum of $S_A$ is $1$, and there are $2^k -1 = 2^{|\mathscr{S} |} -1$ distinct sums $S_A$, therefore \begin{align*} S &= \sum\limits_{A \in \mathscr{P}(\mathscr{S}) \setminus \{\varnothing\}} S_A\ &\geq 1 + 2 + 3 + \cdots +(2^{k}-1)\ & = \frac{2^{k}(2^{k} -1)}{2}\ &= 2^{k-1}(2^k - 1). \end{align*} So \begin{align} 2^{k-1}(2^k - 1) \leq S. \end{align} From (1) and (2) we deduce $$2^{k-1}(2^k - 1) \leq S < 2^{k-1}nk,$$ thus $2^k - 1 < nk$, so $2^k \leq nk$, in contradiction with the hypothesis $2^k >kn$. This shows that there exist two distinct nonempty subsets of $\mathscr{S}$ having equal sums of elements. \end{proof}

Exercise 4.5.6* (Existence of two distinct subsets of $\mathscr{S}$ having equal sums of elements)

Answers

Comments

Exercise 4.5.6* (Existence of two distinct subsets of $\mathscr{S}$ having equal sums of elements)

Answers

Comments

Add answer