I am reading the book "Integer Programming" by Wolsey (1998). In 1.4, the author is counting the number of the feasible subsets of a knapsack problem. The formulation is
$\max \sum_{j=1}^n c_j x_j$
s.t. $\sum_{j=1}^n a_j x_j \leq b.$
In p. 9, the author claims that "The number of subsets is $2^n$. When $b=\sum_{j=1}^n a_j / 2$, at least half of the subsets are feasible, and thus there are at least $2^{n-1}$ feasible subsets." I do not understand where $2^{n-1}$ comes from. Thanks.
Each subset $X$ of things to put into the knapsack (represented by the vector $(x_1,\ldots,x_n) \in \{0,1\}^n$) has a complement subset $\overline{X}$ (all the other things that are not in the first subset), represented by the vector $(1-x_1,\ldots,1-x_n)$.
The claim is that at least one of $X$ and $\overline{X}$ is feasible, and since $\overline{\overline{X}} = X$, that makes at least half of all subsets, so $2^{n-1}$.
To see why this claim is true, we see that
$$2b=\sum_{j=1}^na_j = \sum_{j=1}^n(x_j+1-x_j)a_j = \sum_{j=1}^nx_ja_j + \sum_{j=1}^n(1-x_j)a_j.$$
Both sums on the right hand side of this equation form the left hand side of the feasibility condition, for $X$ and $\overline{X}$, resp. And the equation makes sure they can't both be greater than $b$, so at least one is feasible.