A Thousand Pounds in Bags

A man brings £1000, all in single pound notes, to a bank and asks for it to be split among bags so that, whatever whole sum he later asks for, the teller can hand him some of the bags, unopened, totalling exactly that amount. What is the smallest number of bags that will do, and how many of them hold an odd number of pounds?

Solution

Ten bags suffice, and no fewer. Fill them with $$1, \ 2, \ 4, \ 8, \ 16, \ 32, \ 64, \ 128, \ 256 \quad \text{and} \quad 489,$$ the powers of two up to $256$, with the last bag taking whatever remains, $1000 - 511 = 489$.

The powers of two are the key. Any whole amount from $0$ to $511$ is the sum of a unique selection of $1, 2, 4, \dots, 256$, which is just that amount written in binary. So every request up to $511$ can be met from the first nine bags. For anything from $489$ to $1000$, hand over the $489$ bag and make up the rest, between $0$ and $511$, from the others. Between them the two ranges, $0$ to $511$ and $489$ to $1000$, cover every pound up to $1000$ with no gap.

Why not fewer than ten? With $k$ bags there are only $2^k$ possible selections, and they must produce at least the $1000$ distinct totals $1, 2, \dots, 1000$. Since $2^9 = 512 < 1000 \le 1024 = 2^{10}$, nine bags cannot manage and ten can. As for odd bags, of the ten amounts only $1$ and $489$ are odd, so exactly two bags hold an odd number of pounds.