This is from Henry Dudeney’s “Perplexities” article in the March 1925 issue of
*The Strand Magazine*:

A man went into a bank with 1,000 silver dollars and 10 bags. He said, “Place this money, please, in the bags in such a way that if I call and ask for a certain number of dollars you can hand me over one or more bags, giving me the exact amount called for without opening any of the bags.” How was it to be done? We are, of course, only concerned with a single application, but he may ask for any exact number of dollars from 1 to 1000.

(In the original article it was “sovereigns” and “pounds”—but I’m in the U.S., so…)

This is similar in spirit to Bachet’s Four Weights Problem, so if you’ve solved that one, you should certainly be able to solve this one.

The solution is below Chirico’s *The Mathematicians*.

## The Solution #

Unlike the weights problem, the combination of bags here is strictly additive:

where

So instead of a trinary system, we have a good old binary system. This
means if we have `i`

th bag, we can represent any value between 0 and

Let’s demonstrate this with 3 bags, which should give us the numbers `0:7`

.

```
# fill the bags
bags = vapply(1:3, function(i) {2^(i-1)}, numeric(1))
bags
```

`## [1] 1 2 4`

```
# get all the possible combinations of bags
signs = c(0,1)
S = expand.grid (s1 = signs,
s2 = signs,
s3 = signs) |>
as.matrix()
S
```

```
## s1 s2 s3
## [1,] 0 0 0
## [2,] 1 0 0
## [3,] 0 1 0
## [4,] 1 1 0
## [5,] 0 0 1
## [6,] 1 0 1
## [7,] 0 1 1
## [8,] 1 1 1
```

```
# get the total number of coins for each combination
as.numeric(S %*% bags)
```

`## [1] 0 1 2 3 4 5 6 7`

We have 10 bags, so we can represent any value from 0 to

So the solution is: **The first 9 bags hold coins for from
1 to 9; and the last bag holds 489 coins.**

Let’s verify that.

```
# fill the bags
bags = vapply(1:10, function(i) {2^(i-1)}, numeric(1))
bags[10] = 489 # the last bag is a little short.
# get all the possible combinations of bags
slist = lapply(1:10, function(i) signs)
names(slist) = paste0("bag", 1:10)
S = expand.grid (slist) |> as.matrix()
dim(S)
```

`## [1] 1024 10`

Note that there are still 1024 combinations of bags; we know that we can
only represent the numbers `0:1000`

, so some of the totals will be duplicated.
In other words, for some numbers, there are multiple combinations of
bags that give the same sum.

```
# get the total number of coins for each combination
x = as.numeric(S %*% bags)
# find all the unique values we can achieve
x_unique = sort(unique(x))
# confirm that this gives us every value from 0 to 1000
stopifnot(x_unique==0:1000)
```

So we have achieved the customer’s ask, and the banker is no longer perplexed!

We can go a little further. Which sums can be achieved multiple ways?

`x[duplicated(x)]`

```
## [1] 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507
## [20] 508 509 510 511
```

Note that 489 is the number of coins in bag10, and 511 is

For fun, let’s see the different ways to achieve x = 500

```
ix = which(x==500)
S[ix, ]
```

```
## bag1 bag2 bag3 bag4 bag5 bag6 bag7 bag8 bag9 bag10
## [1,] 0 0 1 0 1 1 1 1 1 0
## [2,] 1 1 0 1 0 0 0 0 0 1
```

The first solution is the "standard" solution, meaning 500 encoded in binary (backwards). The second solution is because our last bag doesn't have the correct number of coins in it, and in fact has fewer than 500. You can tell it's not the standard answer because we use bag 1, meaning the answer appears to be odd. But this evens out, because bag10 has an odd number of coins in it.