Exercise 4.5.11* (Every $x \in \mathbb{Z}/n \mathbb{Z}$ occurs at least once among the sums of the elements of $\mathscr{S}$)

Proof. Let us say that a subset $A\subseteq \mathbb{Z}∕\mathit{n\mathbb{Z}}$ is convenient for some integer $n>0$ if every class modulo $n$ occurs at least once among the sums of the elements of the non empty subsets of $A$.

We will show that for every $n\in [[2^k,2^{k+1}[[$ (so that $k=\lfloor \frac{\log <!--\; FUNCTION\; APPLICATION\; -->(n)}{\log <!--\; FUNCTION\; APPLICATION\; -->(2)}\rfloor$),

(i)

$A=\{\bar{1},\bar{2},{\bar{2}}^2,\dots ,{\bar{2}}^k\}$ is convenient for $n$.

(ii)

Every subset $B\subseteq \mathbb{Z}∕\mathit{n\mathbb{Z}}$ with $k$ elements (or less) is not convenient for $n$.

(i)

Consider the set $A=\{\bar{1},\bar{2},{\bar{2}}^2,\dots ,{\bar{2}}^k\}\subseteq \mathbb{Z}∕\mathit{n\mathbb{Z}}$, where $2^k\le n<2^{k+1}$.

Every residue class modulo $n$ is in the form $\bar{m}$, where $1\le m\le n$. The usual binary representation of $m$ is $m={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i\in I}{2}^i$, where $I\ne \varnothing$, and $I\subseteq [[0,k[[$, since $n<2^{k+1}$ (see Problem 1.2.44). Thus

$$\bar{m}=\underset{i\in I}{\sum }{\bar{2}}^i.$$

This shows that every $\bar{m}\in \mathbb{Z}∕\mathit{n\mathbb{Z}}$ is sum of elements of $A$, so $A$ is convenient for $n$.

(ii)

Suppose now that $B$ satisfies $\mathrm{Card}(B)\le k$, where $2^k\le n<2^{k+1}$. There are $2^{\mathrm{Card}(B)}-1$ non empty subsets of $B$, thus there are at most $2^{\mathrm{Card}(B)}-1$ possible sums of distinct elements of $B$. But $2^{\mathrm{Card}(B)}-1\le 2^k-1<n$, therefore some elements of $\mathbb{Z}∕\mathit{n\mathbb{Z}}$, which has $n$ elements, are not represented by a sum of elements of $B$. So $B$ is not convenient for $n$.

In conclusion, $𝒮=\{\bar{1},\bar{2},{\bar{2}}^2,\dots ,{\bar{2}}^k\}$ is a minimal set of integers having the property that every residue class modulo $n$ occurs at least once among the sums of the elements of the nonempty subsets of $𝒮$.

(Note that there are much more possible sets $𝒮$ with $k+1$ elements.) □